È possibile trovare intersezioni tra un segmento di linea e un insieme disgiunto in log2 (n)?

2

Dato un set S di segmenti di linea 2D disgiunti, c'è un modo per pre-processare S in una struttura dati che può controllare se un singolo segmento arbitrario L interseca qualsiasi segmento in S nel tempo log2 (n), così come modificare la struttura utilizzando gli stessi limiti di complessità temporale?

I punti finali in S sono chiusi e le linee potrebbero avere pendenze.

Le sweep-lines producono prestazioni peggiori di n log n se ogni segmento deve essere aggiunto alla linea prima del controllo e gli indici spaziali come gli alberi ad intervalli non funzioneranno se più segmenti hanno intervalli di coordinate sovrapposti in ogni dimensione e ancora non si interseca. Algoritmi come Shamos Hoey elaborano solo interi gruppi di segmenti.

Si tratta semplicemente di un caso specifico di intersezione rosso-blu con un set di dimensione 1 o può essere utilizzato lo scopo limitato della query per ottenere prestazioni migliori rispetto agli algoritmi generali?

    
posta Aeris130 08.09.2016 - 20:47
fonte

0 risposte

Leggi altre domande sui tag