3.1 Algoritmen gebaseerd op de logaritmische methode
De eerste algoritmen zijn gebaseerd op de toepassing van Bentley’s logaritmische methode . Deze toepassing verscheen voor het eerst in Smid . (Zie ook Schwarz .)
Laat S de huidige verzameling punten in ℝD zijn, en laat n de grootte ervan aanduiden. Schrijf n in het binaire getallenstelsel, n=∑i≥0ai2i, waarbij ai ∈ {0,1}. Verdeel S (willekeurig) in deelverzamelingen: voor elke i zo dat ai = 1 is er een deelverzameling Si, van grootte 2i. Bovendien is er voor elke i zo’n reëel getal δi dat d(S) ≤ δi ≤ d (Si) de gegevensstructuur bestaat uit het volgende.
(1)
Het dichtstbijzijnde paar van S en de afstand δ
(2)
Voor elke i zo dat ai = 1, een δi-rooster dat de punten van Si opslaat. We nemen aan dat de niet-lege cellen van dit rooster in een gebalanceerde binaire zoekboom zijn opgeslagen, lexicografisch gesorteerd volgens hun hoekpunten “linksonder”.
Nu beschouwen we het invoegen van een nieuw punt p. Voor elke i zodanig dat ai = 1, vinden we de cel van het δi-rooster die p bevat samen met de 3D – 1 naburige cellen. Vervolgens berekenen we de afstanden tussen p en alle punten van Si die in deze cellen liggen. Vinden we een afstand kleiner dan δ, dan werken we δ en het dichtstbijgelegen paar bij. Rest ons nog de rest van de gegevensstructuur bij te werken. Zij j de index zodanig dat a0 = a1 = … = aj – 1 en aj = 0. Zij Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 en δj := δ. We bouwen een δj -raster voor de verzameling Sj, en gooien de rasters voor de verzameling S0, S1,… Sj – 1 weg (en maken zo impliciet deze verzamelingen leeg).
Om de juistheid van dit algoritme te bewijzen, merken we op dat aangezien d(S) ≤ δi, het volstaat p te vergelijken met alle punten van Si die in de buurt van p liggen – in het δi-raster. Het dichtstbijzijnde paar wordt dus correct bijgewerkt. Ook voldoet de nieuwe waarde Sj aan d(S ∪ {p}) ≤ δj ≤ d(Sj), en voor alle i > j, hebben we d(S ∪ {p} ≤ δi d(Si). Tenslotte bevat de bijgewerkte datastructuur een rooster waarin voor elke i 2i punten zijn opgeslagen zodat de binaire representatie van n + 1 op positie i een één bevat.
We analyseren de complexiteit van het invoegalgoritme. Merk eerst op dat aangezien δi ≤ d(Si), de buurt van p in het δi -rooster hoogstens een constant aantal punten van Si bevat. We besteden dus O(log n) tijd voor elk rooster. Aangezien de datastructuur een logaritmisch aantal roosters bevat, neemt het eerste deel van het invoegalgoritme O(log 2n) tijd in beslag.
Overweeg het tweede deel van het algoritme, waarin we het δj -rooster bouwen. Deze stap neemt O(|Sj |log |Sj|) tijd in beslag, vanwege het sorteren. Als we de punten echter in een gepaste gesorteerde volgorde opslaan, dan kan dit rooster gebouwd worden in O(|Sj|) = O(2j) tijd. (Zie voor details.) Omdat j elke waarde tussen nul en ⌊log n⌋ kan aannemen, schommelt de invoegtijd sterk. We beweren echter dat de afgeschreven tijd voor de tweede stap begrensd is door O(log n).
Om deze bewering te bewijzen, nemen we aan dat we beginnen met een lege verzameling S en dat we een reeks van n invoegingen uitvoeren. Zij kj het aantal keren dat we tijdens deze invoegingen een rooster bouwen voor een deelverzameling van grootte 2j Dan is kj ten hoogste gelijk aan het aantal gehele getallen bestaande uit ten hoogste 1 + ⌊log n⌋ bits waarvan j minst significante bits gelijk zijn aan één, en waarvan (j + 1)-ste bit gelijk is aan nul. Dat wil zeggen, we hebben
De totale tijd die nodig is voor de tweede stap gedurende de n invoegingen is begrensd door
hetgeen de bewering bewijst.
We hebben laten zien dat de looptijd van het gehele algoritme voor het handhaven van het dichtstbijzijnde paar begrensd is door O(log 2n) worst-case tijd plus O(log n) geamortiseerde tijd per invoeging. Met behulp van standaard technieken (zie Overmars ) kunnen we de datastructuur zo transformeren dat de tweede stap in het ergste geval logaritmische tijd kost. We hebben dus een datastructuur die het dichtstbijzijnde paar bijhoudt in O(log 2n) worst-case tijd per insertie. De structuur heeft grootte O(n).
Merk op dat de eerste stap van het algoritme O(log 2n) tijd vergt, terwijl de tweede stap slechts O(log n) tijd vergt. Dit suggereert dat een verbetering mogelijk is. Inderdaad, in plaats van n in het binaire getallenstelsel te schrijven, gebruiken we het getallenstelsel met basis log n. (Zie Overmars of Schwarz .) Op deze manier nemen beide stappen O(log 2n/log log n) tijd in beslag, terwijl de gebruikte ruimte lineair blijft.
Hiermee hebben we een datastructuur van lineaire grootte die het dichtstbijzijnde paar bijhoudt in O(log2 n /log log n) worst-case tijd per invoeging. Merk op dat het algoritme de bodemfunctie gebruikt om de roostercel te vinden die het nieuwe punt p bevat. Door het rooster te vervangen door een gedegradeerd rooster, kan het algoritme worden geïmplementeerd in het algebraïsche rekenboommodel.
Het is nog steeds mogelijk om de bovenstaande gegevensstructuur te verbeteren. Beschouw opnieuw de datastructuur gebaseerd op de representatie van n in het binaire getallenstelsel. De belangrijkste observatie is de volgende: Als we een punt p invoegen, dan vinden we voor elke i zodanig dat ai = 1, de cel van de δi -gordel die p bevat (plus de naburige cellen). Dat wil zeggen, we voeren puntlocatie-queries uit in een logaritmisch aantal grids, maar steeds met hetzelfde querypunt p. In Schwarz en Smid wordt aangetoond dat de fractionele cascade techniek kan worden uitgebreid zodat al deze queries samen kunnen worden opgelost in O(log n log n) tijd. Het belangrijkste probleem is dat we roosters hebben met verschillende roostergroottes. Daarom moet een ordening op de roostercellen worden ingevoerd die “compatibel” is met al deze afmetingen. Een dergelijke ordening is gedefinieerd. Het resultaat is dat het lokaliseren van het punt p in alle roosters O(log n) vergelijkingen vergt. Aangezien de ordening echter vrij ingewikkeld is, neemt elke vergelijking O(log log n) tijd in beslag. In totaal krijgen we een datastructuur van grootte O(n) die het dichtste paar bijhoudt in O(log n log n) geamortiseerde tijd per invoeging. Merk op dat we de floor functie nodig hebben voor dit resultaat. Dit kan waarschijnlijk worst-case gemaakt worden, maar de details zullen vervelend zijn. Het is niet duidelijk of de ordening op de roostercellen ook gedefinieerd kan worden als we degraded grids gebruiken in plaats van standard grids.
We noemen tenslotte een uitbreiding van de bovenstaande datastructuur. De structuur zoals hierboven beschreven maakt sterk gebruik van het feit dat we alleen punten invoegen. Het blijkt echter dat de structuur kan worden aangepast voor het verwerken van semi-online updates, zoals gedefinieerd door Dobkin en Suri . Een opeenvolging van updates wordt semi-online genoemd als de invoegingen on-line zijn – d.w.z. ze komen in een onbekende volgorde – maar als een punt wordt ingevoegd, wordt ons verteld na hoeveel updates vanaf het moment van inbrengen het zal worden verwijderd. Deze extra informatie over de schrappingen kan gebruikt worden om te garanderen dat wanneer een punt geschrapt wordt, het altijd in een rooster zit dat een kleine deelverzameling opslaat. Omdat bij een schrapping de minimale afstand kan toenemen, slaan we extra informatie op in de datastructuur om het dichtstbijzijnde paar efficiënt bij te werken. Op deze manier krijgen we een datastructuur van grootte O(n) die het dichtste paar bijhoudt in O(log 2n) worst-case tijd per semi-online update. Voor details verwijzen wij de lezer naar Dobkin en Suri en Smid .