Rappresentante efficiente per cerchi in crescita nello spazio 2D?

Question

Immaginate che c'è uno spazio 2D e in questo spazio ci sono cerchi che crescono a velocità costanti differenti. Che cosa è una struttura dati efficiente per la memorizzazione di questi cerchi, in modo tale da poter interrogare "Quali cerchi intersecano il punto p al momento t?".

EDIT: mi rendo conto che ho potuto memorizzare lo stato iniziale dei cerchi in una struttura dati spaziali e fare una query dove si intersecano un cerchio a punto p con un raggio di fastest_growth * t, ma questo non v'è efficiente quando sono alcuni cerchi che crescono molto rapidamente mentre la maggior parte cresce lentamente.

Edit aggiuntive: ho potuto aumentare ulteriormente l'approccio di cui sopra suddividendo i cerchi e raggruppandoli da lì tasso di crescita, quindi applicando il metodo di cui sopra per ciascun gruppo, ma questo richiede un tempo limitato per essere efficace.

Answer 1

Una sorta di spatial index, come ad esempio un quadtree o BSP, vi darà il tempo (log (n)) accesso O.

Ad esempio, ciascun nodo nel quadrifoglio può contenere un elenco collegato di puntatori a tutti quei cerchi che lo intersecano.

Quanti cerchi, a proposito? Per piccoli n, puoi anche solo scorrere su di loro. Se devi aggiornare costantemente il tuo indice spaziale e saltare tutte le linee della cache, potrebbe finire per essere più veloce nel forzarlo.

Answer 2

Come vengono distribuiti i centri delle tue cerchie? Se coprono il piano equamente puoi discretise spazio e nel tempo, quindi effettuano le seguenti operazioni come un passo preelaborazione:

for (t=0; t < max_t; t++) 
    foreach circle c, with centre and radius (x,y,r) at time t 
     for (int X = x-r; X < x+r; x++) 
      for (int Y = x-r; Y < y+r; y++) 
       circles_at[X][Y][T].push_back (&c) 

(supponendo che discretise spazio e nel tempo lungo i confini interi, scala e offset tuttavia è come naturalmente, ed è possibile aggiungere i cerchi in seguito o ammortizzare il costo rinviando calcolo per valori lontani di t)

Poi la query per il punto (x, y) al tempo (t) potrebbe fare un controllo di forza bruta lineare su circles_at[x][y][ceil(t)]

Il trade-off è ovvio, aumentando la risoluzione di una qualsiasi delle Le dimensioni di hree aumentano il tempo di pre-elaborazione, ma ti danno un bucket più piccolo in circles_at[x][y][t] da testare.

Answer 3

Questa è una versione semplificata di un altro problema che ho inviato circa una settimana fa: How to find first intersection of a ray with moving circles

non ho ancora avuto il tempo per descrivere la soluzione che ci si aspettava lì, ma cercherò di delineare esso qui (per questo caso semplice).

L'approccio per risolvere questo problema è utilizzare uno kinetic KD-tree. Se non si ha familiarità con gli alberi di KD, è meglio leggere prima di them. È inoltre necessario aggiungere l'ora come coordinata aggiuntiva (si rende lo spazio 3d anziché 2d). Non ho ancora implementato questa idea, ma credo che questo sia l'approccio corretto.

Answer 4

Le persone faranno molte raccomandazioni sui tipi di indici spaziali da utilizzare, ma vorrei offrire un po 'di consigli ortogonali.

Penso che sia meglio costruire pochi indici in base al tempo, ovvero t_0 < t_1 < t_2 ...

Se un punto interseca un cerchio in t_i, lo intersecherà anche in t_ {i + 1}. Se conosci il punto in anticipo, puoi eliminare tutti i cerchi che intersecano il punto in t_i per tutti i calcoli a t_ {i + 1} e successivi.

Se non si conosce il punto in anticipo, è possibile mantenere questi alberi del punto temporale (costruiti in base alla grandezza di ciascun cerchio in un dato momento). Al momento della query (ad es. T_query), trova i tale che t_ {i-1} < t_query < = t_i. Se controlli tutte le cerchie possibili a t_i, non avrai nessun falso negativo.

Questo è una sorta di modifica per una struttura di dati che è "sensibile alla dinamica del tempo", ma non ne conosco nessuno. Se si dispone di un ambiente con thread, è sufficiente mantenere un indice spaziale e lavorare su quello successivo in background. Ti costerà un sacco di calcoli per il vantaggio di essere in grado di rispondere a query con bassa latenza. Questa soluzione deve essere confrontata almeno alla soluzione O (n) (esaminare ciascun punto e verificare se dist (point, circle.center) < circle.radius).

Answer 5

Rappresentano i cerchi come coni in 3d, dove la terza dimensione è il tempo. Quindi usa un albero BSP per partizionarli il meglio che puoi.

In generale, penso che il caso peggiore per il test dell'intersezione sia sempre O (n), dove n è il numero di cerchi. La maggior parte delle strutture di dati spaziali funzionano partizionando lo spazio in modo intelligente in modo che una frazione degli oggetti (si spera prossima alla metà) si trovi in ​​ciascuna metà. Tuttavia, se gli oggetti si sovrappongono, allora il partizionamento non può essere perfetto; ci saranno sempre casi in cui più di un oggetto si trova in una partizione. Se pensi solo al caso di due cerchi sovrapposti, non c'è modo di disegnare una linea tale che un cerchio sia interamente su un lato e l'altro cerchio sia interamente sull'altro lato. Portati all'estremo logico, assumendo il posizionamento arbitrario dei cerchi e dei raggi arbitrari, non c'è modo di partizionarli in modo tale che il test per l'intersezione prenda O (log (n)).

Ciò non significa che, in pratica, non si otterrà un grande vantaggio dall'utilizzo di un albero, ma il vantaggio che si otterrà dipenderà dalla configurazione dei cerchi e dalla distribuzione delle query.

Answer 6

Mi dispiace che questo non è stato completamente pensato, ma sembra che si possa guardare in Voronoi Diagram (MWVD) con pesi moltiplicativi. Sembra che un avversario possa costringerti a calcolare uno con una serie di query ben piazzate, quindi ho la sensazione che forniscano un limite inferiore al tuo problema.

Supponiamo di calcolare MWVD sui dati di input. Quindi per una query, ti verrà restituito il cerchio che è "più vicino" al tuo punto di query. È quindi possibile determinare se questa circonferenza contiene effettivamente il punto di interrogazione al momento della query. Se non lo fa, allora hai finito: nessuna cerchia contiene il tuo punto. Se lo fa, allora dovresti calcolare MWVD senza quel generatore ed eseguire la stessa query. Potresti essere in grado di calcolare il nuovo MWVD da quello vecchio: la cella contenente il generatore che è stato rimosso deve essere compilata, e sembra (anche se non l'ho dimostrato) che gli unici generatori che possono riempirlo sono i suoi vicini .

Answer 7

Invece di considerare i cerchi, è possibile testare i propri riquadri di delimitazione per filtrare quelli che non contengono il punto. Se i lati del riquadro di delimitazione sono tutti ordinati, si tratta essenzialmente di quattro ricerche binarie.

La parte difficile è ricostruire i lati ordinati per un dato momento, t. Per farlo, puoi iniziare con i punti originali: due elenchi per i lati sinistro e destro con la coordinata x e due elenchi per l'alto e il basso con le coordinate y. Per qualsiasi momento maggiore di 0, tutti i punti laterali a sinistra si sposteranno a sinistra, ecc.Hai solo bisogno di controllare ogni posizione con quella accanto ad essa per ottenere un punto in cui l'elemento e quello accanto sono scambiati. Questo dovrebbe darti un elenco di punti temporali per modificare i tuoi elenchi ordinati. Se ora si ordinano questi record di modifica in base al tempo, per una data ora di inizio e un'ora di fine è possibile estrarre tutti i record di modifica tra i due e applicarli in ordine alle quattro liste. Non ho completamente capito l'algoritmo, ma penso che ci saranno casi limite in cui tre o più elementi successivi possono attraversare esattamente nello stesso momento, quindi potrebbe essere necessario modificare l'algoritmo per gestire anche questi casi limite. Forse un record di modifica dell'elenco che contiene la posizione nell'elenco e il numero di record da riordinare sarebbe sufficiente.

Answer 8

Penso che sia possibile creare un albero binario che risolva questo problema.

Ogni ramo deve contenere un cerchio crescente, un cerchio statico per il partizionamento e l'ora più recente in cui il cerchio del partizionamento partiziona in modo pulito. Inoltre, il cerchio crescente che è contenuto in un nodo dovrebbe sempre avere un tasso di crescita più veloce rispetto a quello dei cerchi crescenti dei nodi figli.

Per eseguire una query, prendere il nodo principale. Innanzitutto controlla se è in crescita, se contiene il punto interrogativo al tempo della query, aggiungilo al set di risposte. Quindi, se il tempo di interrogazione è maggiore del tempo in cui la linea di partizione è interrotta, interrogare entrambi i bambini, altrimenti se il punto rientra nel cerchio di partizionamento, interrogare il nodo sinistro, altrimenti interrogare il nodo destro.

Non ho ancora completato i dettagli di esecuzione degli inserimenti, (la parte difficile è l'aggiornamento del cerchio di partizione in modo che il numero di nodi all'interno e all'esterno sia approssimativamente uguale e il momento in cui la partizione viene interrotta è massimizzata) .

Answer 9

Per combattere i pochi cerchi che si sviluppano rapidamente in caso, è possibile ordinare i cerchi in ordine decrescente per tasso di crescita e controllare ciascuno dei k coltivatori più veloci. Per trovare la giusta k data t, penso che puoi eseguire una ricerca binaria per trovare l'indice k tale che k * m = (t * tasso di crescita di k)^2 dove m è un fattore costante che dovrai trovare per sperimentazione. Il bilanciamento della parte cresce linearmente con k con la parte che cade quadraticamente con il tasso di crescita.

Answer 10

Se, come già suggerito, rappresentano cerchi in crescita per coni verticali in 3d, è possibile suddividere lo spazio come una griglia regolare (può essere esagonale) di cilindri verticali imballati. Per ogni cilindro calcolare le altezze minime e massime (tempi) delle intersezioni con tutti i coni. Se il centro del cerchio (vertice del cono) è posizionato all'interno del cilindro, il tempo minimo è zero. Quindi ordina i coni con il tempo di intersezione minimo. Come risultato di tale indicizzazione, per ogni cilindro avrai la sequenza ordinata di record con 3 valori: tempo minimo, tempo massimo e numero di cerchio.

Quando si controlla un punto nello spazio 3d, si prende il cilindro a cui appartiene e si itera la sua sequenza finché il tempo minimo memorizzato supera il tempo del punto specificato. Tutti i coni ottenuti, il cui tempo massimo è inferiore al dato tempo, sono garantiti per contenere il punto dato. Solo i coni, dove il tempo si trova tra i tempi di intersezione minimi e massimi, sono necessari per ricalcolare.

C'è un compromesso classico tra indicizzazione e costi di runtime: minore è il diametro del cilindro, minore è il range di tempi di intersezione, quindi è necessario ricalcolare un numero inferiore di coni in ogni punto, ma più cilindri devono essere indicizzati. Se i centri del cerchio sono distribuiti in modo non uniforme, allora può valere la pena cercare una configurazione migliore del posizionamento del cilindro, quindi una griglia regolare.

P.S. La mia prima risposta qui - è appena stata registrata per pubblicarla. Spero che non sia tardi.