Il problema è che scorrere un vettore o una lista comporta un tempo O(n)

Se riuscissi ad utilizzare un albero potrei calcolare il tutto in O(lg n). Tuttavia non riesco a trovare una condizione adatta per l'inserimento dei nodi.
Allora ho pensato a un grafo anche se non penso che questo diminuisca di molto il tempo di calcolo. anzi...

Mi hanno suggerito di usare un KD Tree o un BSP Tree o ancora un algoritmo scanline.Però non trovo documentazione valida su queste strutture.
Se qualcuno avesse qualche link mi farebbe un grande favore...