Percorso più breve e punti di ordinamento in uno spazio bidimensionale

Question

Diciamo che ho un oggetto in uno spazio bidimensionale e un insieme di punti che ho bisogno di quell'oggetto da visitare. I punti possono essere aggiunti in qualsiasi momento, ma non rimossi.

Quello che voglio è essere in grado di determinare il prossimo punto più vicino al punto in cui il mio oggetto si trova in O (lg (n)), poi andare ad esso, quindi determinare il prossimo più vicino, ecc ..

Una semplice coda di priorità non funziona perché l'oggetto sta cambiando posizione, quindi la coda dovrebbe essere riorganizzata ogni volta che si sposta. Stavo immaginando di ordinare i punti in un BST in qualche modo, ma non sono sicuro di come ordinare rispetto a (x, y) o se è persino possibile.

Mi sembra che potrei provare a risolvere traveling salesman senza rendermene conto, in tal caso, mi scuso ahah.

Answer 1

Un'opzione consisterebbe nell'utilizzare un albero di partizionamento dello spazio come un albero quadripeso o k-d per memorizzare tutti i punti nello spazio. Queste strutture dati in modo efficiente (di solito in tempo sublinear) supportano le query della forma "qual è il punto più vicino al punto p?" È quindi possibile effettuare le seguenti operazioni:

1. Creare un albero di partizionamento dello spazio per i punti nello spazio.
2. Utilizzare l'albero per trovare il punto p più vicino al punto di partenza.
3. Ripetere quanto segue:
   1. Passare al punto p.
   2. Rimuovere p dall'albero.
   3. Impostare p come il punto più vicino alla posizione corrente.

Spero che questo aiuti!