3.1 Algoritmer baseret på den logaritmiske metode
De første algoritmer er baseret på anvendelse af Bentleys logaritmiske metode . Denne anvendelse optrådte første gang i Smid . (Se også Schwarz .)
Lad S være den aktuelle mængde af punkter i ℝD, og lad n betegne dens størrelse. Skriv n i det binære talsystem, n=i≥0ai2i, hvor ai ∈ {0,1}. S opdeles (vilkårligt) i delmængder: for hvert i, således at ai = 1, findes der en delmængde Si af størrelse 2i. Desuden er der for hvert sådant i et reelt tal δi, således at d(S) ≤ δi ≤ δi ≤ d (Si) datastrukturen består af følgende:
(1)
Det nærmeste par i S og dets afstand δ
(2)
For hvert i, således at ai = 1, et δi -gitter, der lagrer punkterne i Si. Vi antager, at de ikke-tomme celler i dette gitter er gemt i et balanceret binært søgetræ, sorteret leksikografisk efter deres “nederste venstre” hjørne.
Nu betragter vi indsættelsen af et nyt punkt p. For hvert i, således at ai = 1, finder vi den celle i δi-gitteret, der indeholder p sammen med de 3D – 1 naboceller. Derefter beregner vi afstandene mellem p og alle de punkter i Si, der er indeholdt i disse celler. Hvis vi finder en afstand, der er mindre end δ, opdaterer vi δ, og det nærmeste par. Det er stadig nødvendigt at opdatere resten af datastrukturen. Lad j være et sådant indeks, at a0 = a1 = … = … = aj – 1 og aj = 0. Lad Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ … ∪ Sj – 1 og δj := δ. Vi opbygger et δj -gitter for mængden Sj og kasserer gitterne for mængden S0, S1, … Sj – 1 (hvorved vi implicit gør disse mængder tomme).
For at bevise, at denne algoritme er korrekt, skal det bemærkes, at da d(S) ≤ δi, er det tilstrækkeligt at sammenligne p med alle punkter i Si, der ligger i p’s nabolag – i δi-gitteret. Derfor opdateres det nærmeste par korrekt. Den nye værdi Sj opfylder også d(S ∪ {p}) ≤ δj ≤ δj ≤ d(Sj), og for alle i > j har vi d(S ∪ {p} ≤ δi d(Si). Endelig indeholder den opdaterede datastruktur et gitter, der lagrer 2i punkter for hvert i, således at den binære repræsentation af n + 1 indeholder en etter på position i.
Vi analyserer kompleksiteten af indsættelsesalgoritmen. Bemærk først, at eftersom δi ≤ d(Si), indeholder nabolaget til p i δi -gitteret højst et konstant antal punkter i Si. Derfor bruger vi O(log n) tid for hvert gitter. Da datastrukturen indeholder et logaritmisk antal gitre, tager den første del af indsættelsesalgoritmen O(log 2n)-tid.
Se på den anden del af algoritmen, hvor vi opbygger δj -gitteret. Dette trin tager O(|Sj |log |Sjj|) tid på grund af sortering. Hvis vi gemmer punkterne i en passende sorteret rækkefølge, kan dette gitter imidlertid opbygges på O(|Sj|) = O(2j) tid. (Se for detaljer.) Da j kan antage en hvilken som helst værdi mellem nul og ⌊log n⌋, svinger indsættelsestiden meget. Vi hævder imidlertid, at den afskrevne tid for det andet trin er begrænset af O(log n).
For at bevise denne påstand antages det, at vi starter med et tomt sæt S og udfører en sekvens af n indsættelser. Lad kj være antallet af gange, hvor vi under disse indsættelser opbygger et gitter for en delmængde af størrelse 2j Så er kj højst lig med antallet af hele tal bestående af højst 1 + ⌊log n⌋ bits, hvis j mindst betydende bits er lig med et, og hvis (j + 1)-ste bit er lig med nul. Det vil sige, at vi har
Den samlede tid brugt til det andet trin under de n indsættelser er begrænset af
hvilket beviser påstanden.
Vi har vist, at løbetiden for hele algoritmen til opretholdelse af det nærmeste par er afgrænset til O(log 2n) tid i værste tilfælde plus O(log n) afskrevet tid pr. indsættelse. Ved hjælp af standardteknikker (se Overmars ) kan vi omdanne datastrukturen således, at det andet trin tager logaritmisk tid i værste tilfælde. Vi har således en datastruktur, der opretholder det nærmeste par på O(log 2n) worst-case-tid pr. indsættelse. Strukturen har en størrelse O(n).
Bemærk, at det første trin i algoritmen tager O(log 2n) tid, mens det andet trin kun tager O(log n) tid. Dette tyder på, at en forbedring er mulig. I stedet for at skrive n i det binære talsystem bruger vi nemlig talsystemet med base log n. (Se Overmars eller Schwarz .) På denne måde tager begge trin O(log 2n/log log n) tid, mens den anvendte plads forbliver lineær.
Dermed har vi en datastruktur af lineær størrelse, der vedligeholder det nærmeste par i O(log2 n /log log n) worst-case-tid pr. indsættelse. Bemærk, at algoritmen anvender gulvfunktionen for at finde den gittercelle, der indeholder det nye punkt p. Ved at erstatte gitteret med et degraderet gitter kan algoritmen implementeres i den algebraiske beregningstræmodel.
Det er stadig muligt at forbedre ovenstående datastruktur. Overvej igen datastrukturen baseret på repræsentationen af n i det binære talsystem. Den vigtigste iagttagelse er følgende: Hvis vi indsætter et punkt p, finder vi for hvert i, således at ai = 1, den celle i δi -gird, der indeholder p (plus de tilstødende celler). Det vil sige, at vi udfører forespørgsler om punktplacering i et logaritmisk antal gitre, men altid med det samme forespørgselspunkt p. I Schwarz og Smid vises det, at den fraktionelle kaskadeteknik kan udvides, således at alle disse forespørgsler tilsammen kan løses på O(log n log log log n)-tid. Hovedproblemet er, at vi har gitre med forskellige gitterstørrelser. Derfor skal der indføres en rækkefølge for gittercellerne, som er “kompatibel” med alle disse størrelser. I en sådan rækkefølge er defineret. Som følge heraf tager det O(log n) sammenligninger at lokalisere punktet p i alle gitre. Da rækkefølgen er ret kompliceret, tager hver sammenligning imidlertid O(log log log n) tid. Samlet set får vi en datastruktur af størrelse O(n), der opretholder det nærmeste par på O(log n log log log n) afbrudt tid pr. indsættelse. Bemærk, at vi har brug for gulvfunktionen for at opnå dette resultat. Dette kan sandsynligvis gøres worst-case, men detaljerne vil være kedelige. Det er ikke klart, om rækkefølgen på gittercellerne også kan defineres, hvis vi bruger degraderede gitre i stedet for standardgitre.
Vi nævner til sidst en udvidelse af ovenstående datastruktur. Strukturen som beskrevet ovenfor udnytter i høj grad det faktum, at vi kun indsætter punkter. Det viser sig imidlertid, at strukturen kan tilpasses til at håndtere semi-online opdateringer, som defineret af Dobkin og Suri . En sekvens af opdateringer kaldes semi-online, hvis indsættelserne er on-line – dvs. at de ankommer i en ukendt rækkefølge – men når et punkt indsættes, får vi at vide, efter hvor mange opdateringer fra indsættelsestidspunktet det vil blive slettet. Denne ekstra information om sletningerne kan bruges til at garantere, at når et punkt slettes, er det altid indeholdt i et gitter, der lagrer en lille delmængde. Da minimumsafstanden kan stige i forbindelse med en sletning, lagrer vi ekstra oplysninger i datastrukturen for at kunne opdatere det nærmeste par effektivt. På denne måde får vi en datastruktur af størrelse O(n), som vedligeholder det nærmeste par på O(log 2n) worst case-tid pr. semi-online-opdatering. For nærmere oplysninger henvises der til Dobkin og Suri og Smid .