Struttura dei dati efficiente per la distanza euclidea più vicina

Question

La domanda è ispirata al seguente problema UVA: https : //onlinejudge.org/index.php? Opzione= OnlineJudge & AMP; ItemID= 99999999 & Categoria= 18 e Page= show_problem & problema= 1628 .

.

Una rete di stazioni di acquisizione dati autonoma, batteria è stata installata per monitorare il clima nella regione di Amazon. Una stazione di dispacciatura dell'ordine può avviare la trasmissione delle istruzioni per le stazioni di controllo in modo che cambino i loro parametri correnti. Per evitare di sovraccaricare la batteria, ogni stazione (inclusa la stazione dell'ordine) può trasmettere solo altre due stazioni. I destinatari di una stazione sono le due stazioni più vicine. In caso di pareggio, il primo criterio è quello di scegliere il più occidentale (a sinistra sulla mappa), e il secondo criterio è quello di scegliere il più a sud (più basso sulla mappa). Sei commissionato da Amazon State Government di scrivere un programma che decide se, data la localizzazione di ogni stazione, i messaggi possono raggiungere tutte le stazioni.

L'algoritmo ingenuo ovviamente costruirebbe un grafico con le stazioni come vertici e calcola i bordi da un determinato vertice cercando attraverso tutti gli altri vertici per i due più vicini. Quindi, potremmo semplicemente eseguire DFS / BFS. Naturalmente, questo richiede $ o (v ^ 2) $ tempo per costruire il grafico (che passa i casi di test). La mia domanda, tuttavia, è se possiamo costruire il grafico più veloce con una struttura dei dati appropriata. Specificamente, dato un punto di query arbitrario $ P $ e un determinato set di punti $ s $ , possiamo noi Organizza i punti in $ S $ In tal modo che possiamo trovare rapidamente i due punti più vicini in $ s $ a $ p $ (dire, in $ \ log V $ tempo?).

Answer 1

Se lo capisco correttamente, potrebbero essere utilizzati gli indici più spaziali.

Gli indici spaziali hanno in genere circa $ o (log {v}) $ tempo di inserimento e tempo di ricerca simile per i vicini più vicini. Naturalmente puoi creare un diagramma Voronoi da quello, ma puoi anche utilizzare l'indice direttamente per trovare i vicini più vicini ogni volta che ne hai bisogno.

Per la dimensionalità bassa (2D, 3D), le famiglie comuni degli indici spaziali sono kd-alberi (abbastanza semplice e generalmente buono, ma tende ad avere problemi con fitti cluster di punti), quadtrees (un po 'più difficile da implementare perché la precisione numerica può essere complicata) e r-tree (più difficile da implementare, ma dare le migliori prestazioni garantite, in particolare l'albero r * (albero r-stella)).

In caso di utilizzo di C ++, dai un'occhiata a libspatialindex o il Boost r-tree . Se stai usando Java, dai un'occhiata al mio tinspin libreria.

Il termine tecnico per questo è " $ k $ query vicine più vicine" o " $ k $ -Nnn ", con $ k $ Riferendosi al numero di vicini più vicini che si desidera trovare.

Answer 2

Sembra che la struttura dei dati pertinente possa essere un Dynamic Voronoi Diagram . I diagrammi Voronoi sono spesso la risposta quando è coinvolta una serie di punti sull'aereo.

In questo caso, dal momento che il set di punti si sta evolvendo, si desidera una versione dinamica.