3.1 Algoritmi basati sul metodo logaritmico
I primi algoritmi sono basati sull’applicazione del metodo logaritmico di Bentley . Questa applicazione è apparsa per la prima volta in Smid . (Vedi anche Schwarz.)
Lasciamo che S sia l’attuale insieme di punti in ℝD, e che n indichi la sua dimensione. Scriviamo n nel sistema numerico binario, n=∑i≥0ai2i, dove ai ∈ {0,1}. Partizionare S (arbitrariamente) in sottoinsiemi: per ogni i tale che ai = 1 c’è un sottoinsieme Si, di dimensione 2i. Inoltre, per ogni tale i, esiste un numero reale δi tale che d(S) ≤ δi ≤ d (Si) la struttura dei dati consiste in quanto segue.
(1)
La coppia più vicina di S e la sua distanza δ
(2)
Per ogni i tale che ai = 1, una griglia δi che memorizza i punti di Si. Assumiamo che le celle non vuote di questa griglia siano memorizzate in un albero di ricerca binario bilanciato, ordinato lessicograficamente secondo i loro angoli “in basso a sinistra”.
Si consideri ora l’inserimento di un nuovo punto p. Per ogni i tale che ai = 1, troviamo la cella della griglia δi che contiene p insieme alle 3D – 1 celle vicine. Poi calcoliamo le distanze tra p e tutti i punti di Si che sono contenuti in queste celle. Se troviamo una distanza inferiore a δ, allora aggiorniamo δ e la coppia più vicina. Resta da aggiornare il resto della struttura dei dati. Sia j l’indice tale che a0 = a1 = … = aj – 1 e aj = 0. Sia Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 e δj := δ. Costruiamo una griglia δj per l’insieme Sj, e scartiamo le griglie per gli insiemi S0, S1,… Sj – 1 (rendendo così implicitamente vuoti questi insiemi).
Per dimostrare la correttezza di questo algoritmo, si noti che poiché d(S) ≤ δi, è sufficiente confrontare p con tutti i punti di Si che sono nel vicinato di p nella griglia δi. Quindi, la coppia più vicina è aggiornata correttamente. Inoltre, il nuovo valore Sj soddisfa d(S ∪ {p}) ≤ δj ≤ d(Sj), e per tutti gli i > j, abbiamo d(S ∪ {p} ≤ δi d(Si). Infine, la struttura dati aggiornata contiene una griglia che memorizza 2i punti per ogni i tale che la rappresentazione binaria di n + 1 contiene un uno nella posizione i.
Analizziamo la complessità dell’algoritmo di inserimento. Notiamo innanzitutto che poiché δi ≤ d(Si), il quartiere di p nella griglia δi contiene al massimo un numero costante di punti di Si. Quindi, spendiamo O(log n) di tempo per ogni griglia. Poiché la struttura dei dati contiene un numero logaritmico di griglie, la prima parte dell’algoritmo di inserimento richiede O(log 2n) tempo.
Consideriamo la seconda parte dell’algoritmo, in cui costruiamo la griglia δj. Questo passo richiede O(|Sj |log |Sj|) tempo, a causa dell’ordinamento. Se però memorizziamo i punti in un ordine appropriato, allora questa griglia può essere costruita in O(|Sj|) = O(2j) tempo. (Poiché j può assumere qualsiasi valore tra zero e ⌊log n⌋, il tempo di inserimento oscilla ampiamente. Affermiamo, tuttavia, che il tempo ammortizzato per il secondo passo è delimitato da O(log n).
Per dimostrare questa affermazione, supponiamo di iniziare con un insieme vuoto S ed eseguire una sequenza di n inserimenti. Sia kj il numero di volte che, durante queste inserzioni, costruiamo una griglia per un sottoinsieme di dimensione 2j Allora kj è al massimo uguale al numero di interi composti al massimo da 1 + ⌊log n⌋ bit i cui j bit meno significativi sono uguali a uno, e il cui (j + 1)-st bit è uguale a zero. Cioè, abbiamo
Il tempo totale speso per il secondo passo durante gli n inserimenti è limitato da
che prova l’affermazione.
Abbiamo dimostrato che il tempo di esecuzione dell’intero algoritmo per il mantenimento della coppia più vicina è delimitato da O(log 2n) tempo del caso peggiore più O(log n) tempo ammortizzato per inserimento. Usando tecniche standard (vedi Overmars ), possiamo trasformare la struttura dei dati in modo che il secondo passo richieda tempo logaritmico nel caso peggiore. Quindi, abbiamo una struttura di dati che mantiene la coppia più vicina in O(log 2n) tempo di caso peggiore per inserimento. La struttura ha dimensione O(n).
Nota che il primo passo dell’algoritmo richiede tempo O(log 2n), mentre il secondo passo richiede solo tempo O(log n). Questo suggerisce che un miglioramento è possibile. Infatti, invece di scrivere n nel sistema di numeri binari, usiamo il sistema di numeri con base log n. (Vedere Overmars o Schwarz .) In questo modo, entrambi i passi richiedono O(log 2n/log log n) tempo, mentre lo spazio utilizzato rimane lineare.
Da qui, abbiamo una struttura dati di dimensione lineare che mantiene la coppia più vicina in O(log2 n /log log n) tempo peggiore per inserimento. Si noti che l’algoritmo utilizza la funzione floor per trovare la cella della griglia che contiene il nuovo punto p. Sostituendo la griglia con una griglia degradata, l’algoritmo può essere implementato nel modello di calcolo algebrico ad albero.
È ancora possibile migliorare la struttura dati di cui sopra. Consideriamo di nuovo la struttura dei dati basata sulla rappresentazione di n nel sistema di numeri binari. L’osservazione principale è la seguente: Se inseriamo un punto p, allora per ogni i tale che ai = 1, troviamo la cella del δi -gird che contiene p (più le celle vicine). Cioè, eseguiamo interrogazioni di localizzazione dei punti in un numero logaritmico di griglie, ma sempre con lo stesso punto p. In Schwarz e Smid , si dimostra che la tecnica a cascata frazionata può essere estesa in modo che tutte queste interrogazioni insieme possano essere risolte in tempo O(log n log n). Il problema principale è che abbiamo griglie con dimensioni diverse. Pertanto, è necessario introdurre un ordinamento sulle celle della griglia che sia “compatibile” con tutte queste dimensioni. In tale ordinamento è definito. Come risultato, la localizzazione del punto p in tutte le griglie richiede O(log n) confronti. Poiché l’ordinamento è abbastanza complicato, tuttavia, ogni confronto richiede O(log log n) tempo. Nel complesso, otteniamo una struttura dati di dimensione O(n) che mantiene la coppia più vicina in O(log n log n) tempo ammortizzato per inserimento. Notate che abbiamo bisogno della funzione floor per questo risultato. Questo può probabilmente essere fatto nel caso peggiore, ma i dettagli saranno noiosi. Non è chiaro se l’ordinamento sulle celle della griglia può anche essere definito se usiamo griglie degradate invece di griglie standard.
Infine menzioniamo un’estensione della struttura dati di cui sopra. La struttura come descritta sopra sfrutta pesantemente il fatto che inseriamo solo punti. Si scopre, tuttavia, che la struttura può essere adattata per trattare gli aggiornamenti semi-online, come definito da Dobkin e Suri . Una sequenza di aggiornamenti è chiamata semi-online se gli inserimenti sono on-line – cioè, arrivano in un ordine sconosciuto – ma quando un punto viene inserito, ci viene detto dopo quanti aggiornamenti dal momento dell’inserimento sarà cancellato. Questa informazione extra sulle cancellazioni può essere usata per garantire che quando un punto viene cancellato, è sempre contenuto in una griglia che memorizza un piccolo sottoinsieme. Poiché in una cancellazione la distanza minima può aumentare, memorizziamo informazioni extra nella struttura dei dati per aggiornare la coppia più vicina in modo efficiente. In questo modo, otteniamo una struttura di dati di dimensione O(n) che mantiene la coppia più vicina in O(log 2n) tempo peggiore per aggiornamento semi-online. Per i dettagli, rimandiamo il lettore a Dobkin e Suri e Smid.