3.1 Algoritmer baserade på den logaritmiska metoden
De första algoritmerna bygger på Bentleys logaritmiska metod . Denna tillämpning förekom för första gången i Smid . (Se även Schwarz .)
Låt S vara den aktuella mängden punkter i ℝD och låt n beteckna dess storlek. Skriv n i det binära talsystemet, n=∑i≥0ai2i, där ai ∈ {0,1}. Dela upp S (godtyckligt) i delmängder: för varje i så att ai = 1 finns det en delmängd Si, av storlek 2i. Dessutom finns det för varje sådan i ett verkligt tal δi så att d(S) ≤ δi ≤ d (Si) datastrukturen består av följande:
(1)
Det närmaste paret i S och dess avstånd δ
(2)
För varje i så att ai = 1, ett δi -galler som lagrar punkterna i Si. Vi antar att de icke-tomma cellerna i detta rutnät lagras i ett balanserat binärt sökträd, som sorteras lexikografiskt enligt deras ”nedre vänstra” hörn.
Nu betraktar vi införandet av en ny punkt p. För varje i så att ai = 1, finner vi den cell i δi-rutnätet som innehåller p tillsammans med 3D – 1 granncellerna. Därefter beräknar vi avstånden mellan p och alla punkter i Si som ingår i dessa celler. Om vi hittar ett avstånd som är mindre än δ uppdaterar vi δ och det närmaste paret. Det återstår att uppdatera resten av datastrukturen. Låt j vara det index som gör att a0 = a1 = … = aj – 1 och aj = 0. Låt Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 och δj := δ. Vi bygger ett δj -galler för mängden Sj och kastar gallren för mängden S0, S1, … Sj – 1 (och gör därmed implicit dessa mängder tomma).
För att bevisa att denna algoritm är korrekt, observera att eftersom d(S) ≤ δi räcker det med att jämföra p med alla punkter i Si som ligger i p:s grannskap – i δi-gallret. Därför uppdateras det närmaste paret korrekt. Det nya värdet Sj uppfyller dessutom d(S ∪ {p}) ≤ δj ≤ d(Sj), och för alla i > j har vi d(S ∪ {p} ≤ δi d(Si). Slutligen innehåller den uppdaterade datastrukturen ett rutnät som lagrar 2i punkter för varje i så att den binära representationen av n + 1 innehåller en etta på position i.
Vi analyserar komplexiteten hos insättningsalgoritmen. Observera först att eftersom δi ≤ d(Si) innehåller grannskapet till p i δi -nätet högst ett konstant antal punkter i Si. Därför spenderar vi O(log n) tid för varje rutnät. Eftersom datastrukturen innehåller ett logaritmiskt antal rutnät tar den första delen av insättningsalgoritmen O(log 2n) tid.
Besök den andra delen av algoritmen, där vi bygger δj -rutnätet. Detta steg tar O(|Sj |log |Sjj|) tid, på grund av sortering. Om vi lagrar punkterna i en lämplig sorterad ordning kan dock detta rutnät byggas på O(|Sj|) = O(2j) tid. (Se för detaljer.) Eftersom j kan ta vilket värde som helst mellan noll och ⌊log n⌋ fluktuerar insättningstiden kraftigt. Vi hävdar dock att den avskrivna tiden för det andra steget är begränsad till O(log n).
För att bevisa detta påstående antar vi att vi börjar med en tom mängd S och utför en sekvens av n insättningar. Låt kj vara antalet gånger som vi under dessa insättningar bygger ett rutnät för en delmängd av storlek 2j Då är kj högst lika med antalet heltal som består av högst 1 + ⌊log n⌋ bitar vars j minst signifikanta bitar är lika med ett och vars (j + 1)-sta bit är lika med noll. Det vill säga, vi har
Den totala tidsåtgången för det andra steget under de n insatserna begränsas av
vilket bevisar påståendet.
Vi har visat att körtiden för hela algoritmen för att bibehålla det närmaste paret är begränsad till O(log 2n) i värsta fall plus O(log n) avskriven tid per insättning. Med hjälp av standardtekniker (se Overmars ) kan vi omvandla datastrukturen så att det andra steget tar logaritmisk tid i värsta fall. Vi har alltså en datastruktur som upprätthåller det närmaste paret på O(log 2n) värsta tid per inmatning. Strukturen har storlek O(n).
Bemärk att det första steget i algoritmen tar O(log 2n) tid, medan det andra steget endast tar O(log n) tid. Detta tyder på att en förbättring är möjlig. I stället för att skriva n i det binära talsystemet använder vi nämligen talsystemet med basen log n. (Se Overmars eller Schwarz .) På detta sätt tar båda stegen O(log 2n/log log n) tid, medan det använda utrymmet förblir linjärt.
Därmed har vi en datastruktur av linjär storlek som upprätthåller det närmaste paret i O(log2 n /log log n) värsta falltid per insättning. Observera att algoritmen använder golvfunktionen för att hitta den nätcell som innehåller den nya punkten p. Genom att ersätta nätet med ett försämrat nät kan algoritmen implementeras i den algebraiska beräkningsträdmodellen.
Det är fortfarande möjligt att förbättra ovanstående datastruktur. Betrakta återigen datastrukturen som bygger på representationen av n i det binära talsystemet. Den viktigaste iakttagelsen är följande: Om vi lägger in en punkt p, så hittar vi för varje i så att ai = 1 den cell i δi -gird som innehåller p (plus de angränsande cellerna). Det vill säga, vi utför punktplaceringsförfrågningar i ett logaritmiskt antal rutnät, men alltid med samma förfrågningspunkt p. I Schwarz och Smid visas att den fraktionella kaskadtekniken kan utvidgas så att alla dessa förfrågningar tillsammans kan lösas på O(log n log log log n)-tid. Huvudproblemet är att vi har rutnät med olika rutstorlekar. Därför måste man införa en ordning på nätcellerna som är ”kompatibel” med alla dessa storlekar. En sådan ordning är definierad. Som ett resultat av detta krävs det O(log n) jämförelser för att lokalisera p-punkten i alla rutnät. Eftersom ordningen är ganska komplicerad tar dock varje jämförelse O(log log n) tid. Sammantaget får vi en datastruktur av storlek O(n) som upprätthåller det närmaste paret i O(log n log log log n) avskriven tid per insättning. Observera att vi behöver golvfunktionen för detta resultat. Detta kan förmodligen göras i värsta fall, men detaljerna kommer att vara tråkiga. Det är inte klart om ordningen på rutnätscellerna också kan definieras om vi använder degraderade rutnät i stället för standardrutnät.
Vi nämner slutligen en utvidgning av ovanstående datastruktur. Strukturen som beskrivs ovan utnyttjar i hög grad det faktum att vi endast infogar punkter. Det visar sig dock att strukturen kan anpassas för att hantera semi-onlineuppdateringar, enligt Dobkin och Suri . En sekvens av uppdateringar kallas semi-online om inläggen är on-line – dvs. de anländer i en okänd ordning – men när en punkt läggs in får vi veta efter hur många uppdateringar från tidpunkten för inlägget den kommer att tas bort. Denna extra information om borttagningarna kan användas för att garantera att när en punkt tas bort finns den alltid med i ett rutnät som lagrar en liten delmängd. Eftersom det minsta avståndet kan öka vid en radering, lagrar vi extra information i datastrukturen för att uppdatera det närmaste paret på ett effektivt sätt. På detta sätt får vi en datastruktur av storlek O(n) som upprätthåller det närmaste paret i värsta fall på O(log 2n) värsta falltid per semi-onlineuppdatering. För detaljer hänvisar vi läsaren till Dobkin, Suri och Smid .
.