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?