3.1 Algoritmi bazați pe metoda logaritmică
Primii algoritmi se bazează pe aplicarea metodei logaritmice a lui Bentley . Această aplicație a apărut pentru prima dată în Smid . (A se vedea și Schwarz .)
Să fie S setul curent de puncte din ℝD și să se noteze n mărimea sa. Scrieți n în sistemul de numere binare, n=∑i≥0ai2i, unde ai ∈ {0,1}. Se împarte S (în mod arbitrar) în subansambluri: pentru fiecare i astfel încât ai = 1 există un subansamblu Si, de dimensiune 2i. Mai mult, pentru fiecare astfel de i, există un număr real δi astfel încât d(S) ≤ δi ≤ d (Si) structura de date constă în următoarele:
(1)
Cea mai apropiată pereche din S și distanța δ
(2)
Pentru fiecare i astfel încât ai = 1, o grilă δi care stochează punctele din Si. Presupunem că celulele nevide ale acestei grile sunt stocate într-un arbore de căutare binar echilibrat, ordonate lexicografic în funcție de colțurile lor „stânga jos”.
Considerăm acum inserarea unui nou punct p. Pentru fiecare i astfel încât ai = 1, găsim celula din δi-grila care conține p împreună cu cele 3D – 1 celule vecine. Apoi calculăm distanțele dintre p și toate punctele din Si care sunt conținute în aceste celule. Dacă găsim o distanță mai mică decât δ, atunci actualizăm δ, iar cea mai apropiată pereche. Rămâne să actualizăm restul structurii de date. Fie j indicele astfel încât a0 = a1 = … = aj – 1 și aj = 0. Fie Sj := {p}. ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 și δj := δ. Construim o grilă δj pentru setul Sj, și eliminăm grilele pentru setul S0, S1,… Sj – 1 (făcând astfel implicit aceste seturi goale).
Pentru a demonstra corectitudinea acestui algoritm, observăm că, din moment ce d(S) ≤ δi, este suficient să comparăm p cu toate punctele din Si care se află în vecinătatea lui p – în grila δi. Prin urmare, cea mai apropiată pereche este actualizată corect. De asemenea, noua valoare Sj satisface d(S ∪ {p}) ≤ δj ≤ d(Sj), iar pentru toți i > j, avem d(S ∪ {p} ≤ δi d(Si). În cele din urmă, structura de date actualizată conține o grilă care stochează 2i puncte pentru fiecare i astfel încât reprezentarea binară a lui n + 1 să conțină un unu în poziția i.
Analizăm complexitatea algoritmului de inserție. Mai întâi observăm că, deoarece δi ≤ d(Si), vecinătatea lui p în grila δi conține cel mult un număr constant de puncte din Si. Prin urmare, cheltuim O(log n) timp pentru fiecare grilă. Deoarece structura de date conține un număr logaritmic de grile, prima parte a algoritmului de inserție durează O(log 2n) timp.
Considerăm a doua parte a algoritmului, în care construim δj -grila. Această etapă durează O(|Sj |log |Sj|) timp, din cauza sortării. Cu toate acestea, dacă stocăm punctele într-o ordine de sortare adecvată, atunci această grilă poate fi construită în O(|Sj|) = O(2j) timp. (A se vedea pentru detalii.) Deoarece j poate lua orice valoare între zero și ⌊log n⌋, timpul de inserție fluctuează foarte mult. Cu toate acestea, afirmăm că timpul amortizat pentru a doua etapă este mărginit de O(log n).
Pentru a demonstra această afirmație, presupunem că începem cu un set gol S și efectuăm o secvență de n inserții. Fie kj numărul de ori când, în timpul acestor inserții, construim o grilă pentru un subansamblu de dimensiune 2j Atunci kj este cel mult egal cu numărul de numere întregi formate din cel mult 1 + ⌊log n⌋ biți ai căror j biți cel mai puțin semnificativi sunt egali cu unu și al căror (j + 1)-st bit este egal cu zero. Adică, avem
Timpul total petrecut pentru al doilea pas în timpul celor n inserții este mărginit de
ceea ce dovedește afirmația.
Am arătat că timpul de execuție al întregului algoritm de menținere a celei mai apropiate perechi este delimitat de O(log 2n) timp în cel mai rău caz plus O(log n) timp amortizat per inserție. Folosind tehnici standard (a se vedea Overmars ), putem transforma structura de date astfel încât al doilea pas să dureze un timp logaritmic în cel mai rău caz. Prin urmare, avem o structură de date care menține cea mai apropiată pereche în O(log 2n) timp în cel mai rău caz pentru fiecare inserție. Structura are dimensiunea O(n).
Rețineți că prima etapă a algoritmului durează O(log 2n) timp, în timp ce a doua etapă durează doar O(log n) timp. Acest lucru sugerează că este posibilă o îmbunătățire. Într-adevăr, în loc să scriem n în sistemul de numere binare, folosim sistemul de numere cu baza log n. (A se vedea Overmars sau Schwarz .) În acest fel, ambele etape durează O(log 2n/log log n) timp, în timp ce spațiul utilizat rămâne liniar.
În consecință, avem o structură de date de dimensiune liniară care menține cea mai apropiată pereche în O(log2 n /log log n) timp în cel mai rău caz per inserție. Rețineți că algoritmul utilizează funcția floor pentru a găsi celula de grilă care conține noul punct p. Prin înlocuirea grilei cu o grilă degradată, algoritmul poate fi implementat în modelul arborelui de calcul algebric.
Este încă posibil să se îmbunătățească structura de date de mai sus. Să considerăm din nou structura de date bazată pe reprezentarea lui n în sistemul de numere binare. Observația principală este următoarea: Dacă introducem un punct p, atunci pentru fiecare i astfel încât ai = 1, găsim celula din δi -gird care conține p (plus celulele învecinate). Altfel spus, efectuăm interogări de localizare a punctelor într-un număr logaritmic de grile, dar întotdeauna cu același punct de interogare p. În Schwarz și Smid , se arată că tehnica de cascadă fracționară poate fi extinsă astfel încât toate aceste interogări împreună să poată fi rezolvate în timp O(log n log log n). Principala problemă constă în faptul că avem grile cu dimensiuni diferite. Prin urmare, trebuie introdusă o ordonare a celulelor grilei care să fie „compatibilă” cu toate aceste dimensiuni. Într-o astfel de ordonare se definește o astfel de ordine. Ca urmare, localizarea punctului p în toate grilele durează O(log n) comparații. Cu toate acestea, deoarece ordonarea este destul de complicată, fiecare comparație necesită un timp O(log log n). În general, obținem o structură de date de dimensiune O(n) care păstrează cea mai apropiată pereche în O(log n log log n) timp amortizat pentru fiecare inserție. Rețineți că avem nevoie de funcția floor pentru acest rezultat. Acest lucru poate fi probabil realizat în cel mai rău caz, dar detaliile vor fi plictisitoare. Nu este clar dacă ordonarea pe celulele grilei poate fi de asemenea definită dacă folosim grile degradate în loc de grile standard.
În final menționăm o extensie a structurii de date de mai sus. Structura așa cum a fost descrisă mai sus folosește foarte mult faptul că inserăm doar puncte. Cu toate acestea, se pare că structura poate fi adaptată pentru a face față actualizărilor semi-online, așa cum sunt definite de Dobkin și Suri . O secvență de actualizări se numește semi-online dacă inserțiile sunt on-line – adică sosesc într-o ordine necunoscută – dar atunci când un punct este inserat, ni se spune după câte actualizări din momentul inserției va fi șters. Aceste informații suplimentare despre ștergeri pot fi utilizate pentru a garanta că, atunci când un punct este șters, acesta este întotdeauna conținut într-o grilă care stochează un subset mic. Deoarece, în cazul unei ștergeri, distanța minimă poate crește, stocăm informații suplimentare în structura de date pentru actualizarea eficientă a celei mai apropiate perechi. În acest fel, obținem o structură de date de dimensiune O(n) care menține cea mai apropiată pereche în O(log 2n) timp în cel mai rău caz pentru fiecare actualizare semi-online. Pentru detalii, trimitem cititorul la Dobkin și Suri și Smid .
.