Struttura dei dati per supportare una determinata query su un insieme di 2D punti

Question

Ho una serie di punti 2D, e voglio essere in grado di fare la seguente query con argomenti x_min e n: quali sono i n punti con grande y che avere x > x_min?

di riformulare in Ruby:

class PointsThing 
    def initialize(points) 
    @points = points 
    end 

    def query(x_min, n) 
    @points.select { |point| point.x > x_min }.sort_by { |point| point.y }.take(n) 
    end 
end 

Idealmente, la mia classe avrebbe anche sostenere un inserto e cancellare il funzionamento.

Non riesco a pensare a una struttura dati per questo che consentirebbe l'esecuzione della query in meno di tempo O (| @points |). Qualcuno ne conosce uno?

Answer 1

Ordinare i punti per x decrescente. Per ogni punto in ordine, inserirlo in un albero rosso-nero purely functional ordinato da y decrescente. Mantieni tutti gli alberi intermedi in un array.

Per cercare un particolare x_min, utilizzare la ricerca binaria per trovare l'albero intermedio in cui sono stati inseriti esattamente i punti con x> x_min. Attraversa questo albero per trovare i primi n punti.

Il costo di preelaborazione è O (p log p) in tempo e spazio, dove p è il numero di punti. Il tempo di interrogazione è O (log p + n), dove n è il numero di punti da restituire nella query.

Answer 2

Se i tuoi dati non sono ordinati, non hai altra scelta che controllare ogni punto poiché non puoi sapere se esiste un altro punto per cui y è maggiore di tutti gli altri punti e per il quale x > x_min. In breve: non puoi sapere se un altro punto dovrebbe essere incluso se non li controlli tutti.

In questo caso, suppongo che sarebbe impossibile controllare il tempo lineare sub come richiesto, poiché è necessario verificarli tutti. Il modo migliore per cercare tutto sarebbe lineare.

Se i dati sono ordinati, il tuo caso migliore sarà il tempo costante (tutti i n punti sono quelli con il massimo y) e il caso peggiore sarebbe lineare (tutti i n punti sono quelli con meno y). Il caso medio sarebbe più vicino alla costante, penso che se x e x_min siano entrambi casualmente all'interno di un intervallo specifico.

Se si desidera ridimensionare (ovvero, si potrebbero avere valori elevati di n), si desidera mantenere ordinato anche il set risultante poiché è necessario verificare i nuovi potenziali punti contro di esso e rilasciare il valore più basso valore quando si inserisce (se dimensioni> n). Usando un albero, questo può essere il tempo di registrazione.

Quindi, per fare l'intera cosa, il caso peggiore è per i punti non ordinati, nel qual caso stai guardando il tempo di nlog (n). I punti ordinati sono migliori, nel qual caso stai guardando il caso medio di log (n) (di nuovo, assumendo valori distribuiti approssimativamente a caso per x e x_min), che sì è sub-lineare.

---

Nel caso in cui non lo è in un primo momento ovvio perché i punti ordinati avranno hanno costante di tempo per la ricerca in, andrò oltre che qui in fretta.

Se i n punti con i maggiori valori di y avevano tutti x > x_min (il migliore dei casi), allora stai semplicemente afferrando ciò che ti serve al di fuori, in modo che il caso sia ovvio.

Per il caso medio, assumendo approssimativamente a caso distribuito x e x_min, le probabilità che x > x_min siano sostanzialmente la metà. Per qualsiasi due numeri casuali a e b, a > b è altrettanto probabile che sia vero come b > a. Questa è la stessa cosa con x e x_min; È altrettanto probabile che x > x_min sia vero come x_min > x, ovvero 0,5 probabilità. Ciò significa che, per i tuoi punti, in media ogni secondo punto controllato soddisferà il tuo requisito x > x_min, quindi in media controllerai 2n punti per trovare i n punti più alti che soddisfano i tuoi criteri. Quindi il caso migliore era c tempo, la media è 2c che è ancora costante.

Si noti, tuttavia, che per i valori di n che si avvicinano alla dimensione dell'insieme, ciò nasconde il fatto che si sta attraversando l'intero set, riportandolo essenzialmente indietro al tempo lineare.Quindi la mia affermazione che è un tempo costante non è vera se si assumono valori casuali di n entro l'intervallo della dimensione del set.

Se questa non è una domanda puramente accademica ed è motivata da qualche necessità effettiva, dipende dalla situazione.

(modifica) Ho appena realizzato che le mie asserzioni a tempo costante presupponevano una struttura dati in cui si ha accesso diretto al valore più alto e possono passare in sequenza a valori più bassi. Se la struttura dei dati che ti viene fornita non corrisponde a quella descrizione, ovviamente questo non sarà il caso.

Answer 3

In questo caso, alcune precomputazioni potrebbero essere d'aiuto.

Prima partizione il set di punti che prendono x_min come elemento di rotazione.

Poi per insieme di punti che si trovano sul lato destro della x_min costruire un max_heap sulla base di y coordinate.

Ora eseguire la query come: Eseguire n operazioni extract_max sul max_heap predefinito.

Il tempo di esecuzione della query sarebbe registro X + log (X-1) + ..... log (X (n-1))

registro X: Per la prima operazione di estrazione massima.

log X-1: per la seconda operazione di estrazione massima e così via.

X: dimensione dell'heap massimo originale.

Anche nel caso peggiore quando il n < < X, Il tempo impiegato sarebbe O (n log X).

Answer 4

Notation

Sia P l'insieme dei punti.

Sia top_y (n, x_min) descrivono la query per raccogliere i n punti da P con maggiori coordinate y tra quelli con coordinata x maggiore o uguale a `x_min'.

Lascia che sia x_0 il numero minimo di coordinate x nel set di punti. Partizionare l'asse x a destra di x_0 in un insieme di intervalli aperti a destra, chiusi e aperti I_i mediante l'insieme di coordinate x del set di punti P tale che min(I_i) è il i -th ma la più piccola x coordinata da P. Definire il rango di coordinate r(x) di x come l'indice dell'intervallo x è un elemento di o 0 se x < x_0.

Si noti che r(x) può essere calcolato in O(log #({I_i})) utilizzando un albero di ricerca binario.

Simple Solution

1. Trova le set point diminuendo coordinate y e conservare questo array A nel tempo e nello spazio O(#P log #P)O(#P).

2. processo ogni query top_y (n, x_min) attraversando questo array in ordine, saltando gli articoli A_i: A_i.x < x_0, contando tutte le altre voci finché il contatore raggiunge n o sei a fine A. Questa elaborazione richiede lo spazio O(n) e lo spazio O(1).

Si noti che questo potrebbe già essere sufficiente: Interroga top_y (n_0, a_0); a_0 < min { p.x | p \in P }, n_0 = c * #P, c = const richiedono il passaggio 1 in ogni caso e per n << #P e 'infrequente' interroga ulteriori ottimizzazioni erano non vale la pena.

osservazione

1. consideri lo sequenze s_i, s_ (i + 1) of points with x-coordinates greater than or equal to min (I_i), min (I_ (i + 1)) , ordered by decreasing y-coordinate. s_ (i + 1) is a strict subsequence of s_i`.

2. Se p_1 \in s_(i+1) e p_2.x >= p_1.x quindi p_2 \in s_(i+1).

raffinato Soluzione

Una struttura dati raffinata consente il tempo di elaborazione O(n) + O(log #P) query.

Annotare la matrice A dalla soluzione semplice con una "spedizione successiva" per gli elementi precisamente A_i con A_(i+1).x < A_i.x; Questi dati di spedizione consisterebbero in un array disp:[r(A_(i+1).x) + 1 .. r(A_i.x)] di A -indexes dell'elemento successivo in A i cui ranghi di coordinate x almeno pari all'indice in disp. Gli indici di spedizione indicati sono sufficienti per l'elaborazione della query, poiché ...

• ... disp[j] = disp[r(A_(i+1).x) + 1] per ogni j <= r(A_(i+1).x).
• ... per qualsiasi x_min con r(x_min) > r(A_i.x), l'algoritmo non sarebbe qui

L'indice corretto per accedere disp è r(x_min) che rimane costante durante una query e prende O(log #P) per calcolare una volta per query mentre il così la selezione dell'indice è O(1) ad ogni elemento A.

disp può essere precalcolata. Non esistono due voci disp su tutti gli array disp identici (la prova è saltata, ma è facile [;-)] vedere data la costruzione). Pertanto la costruzione degli array disp può essere eseguita in stack in un'unica scansione attraverso il set di punti ordinato in A.Poiché vi sono voci #P, la struttura disp occupa lo spazio O(#P) e il tempo di costruzione O(#P) per essere dominata dai requisiti di spazio e tempo per l'ordinamento y. Quindi, in un certo senso, questa struttura viene gratis.

requisiti di tempo per interrogare top_y(n,x_min)

• Computing r(x_min): O(log #P);
• Passaggio tramite A: O(n);