3.1 Logaritmimenetelmään perustuvat algoritmit
Ensimmäiset algoritmit perustuvat Bentleyn logaritmimenetelmän soveltamiseen. Tämä sovellus ilmestyi ensimmäisen kerran Smidissä . (Katso myös Schwarz .)
Olkoon S ℝD:n nykyinen pistejoukko ja merkitään n sen kokoa. Kirjoitetaan n binäärilukujärjestelmässä n=∑i≥0ai2i, missä ai ∈ {0,1}. Jaetaan S (mielivaltaisesti) osajoukkoihin: jokaiselle i:lle siten, että ai = 1, on olemassa yksi osajoukko Si, jonka koko on 2i. Lisäksi jokaiselle tällaiselle i:lle on reaaliluku δi siten, että d(S) ≤ δi ≤ d (Si) Tietorakenne koostuu seuraavista:
(1)
S:n lähin pari ja sen etäisyys δ
(2)
Kullekin i:lle siten, että ai = 1, δi -ruutu, johon tallennetaan Si:n pisteet. Oletamme, että tämän ruudukon ei-tyhjät solut on tallennettu tasapainotettuun binääriseen hakupuuhun, joka on lajiteltu leksikografisesti ”vasemman alakulman” mukaan.
Harkitaan nyt uuden pisteen p lisäämistä. Jokaiselle i:lle, joka on sellainen, että ai = 1, etsitään δi-ristikon solu, joka sisältää p:n yhdessä 3D – 1:n naapurisolun kanssa. Sitten lasketaan etäisyydet p:n ja kaikkien näihin soluihin sisältyvien Si:n pisteiden välillä. Jos etäisyys on pienempi kuin δ, päivitetään δ ja lähin pari. Jäljelle jää muun tietorakenteen päivittäminen. Olkoon j sellainen indeksi, että a0 = a1 = … = aj – 1 ja aj = 0. Olkoon Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 ja δj := δ. Rakennetaan δj -ruutu joukolle Sj ja hylätään ruudut joukoille S0, S1,… Sj – 1 (jolloin näistä joukoista tulee implisiittisesti tyhjiä).
Todistaaksemme tämän algoritmin oikeellisuuden huomaa, että koska d(S) ≤ δi, riittää, että verrataan p:tä kaikkiin Si:n pisteisiin, jotka ovat p:n naapurustossa – δi-ruudussa. Näin ollen lähin pari päivitetään oikein. Myös uusi arvo Sj täyttää d(S ∪ {p}) ≤ δj ≤ d(Sj), ja kaikille i > j, meillä on d(S ∪ {p} ≤ δi d(Si). Lopuksi päivitetty tietorakenne sisältää ruudukon, johon tallennetaan 2i pistettä jokaiselle i:lle siten, että n + 1:n binäärikuvaus sisältää ykkösen paikassa i.
Analysoimme lisäysalgoritmin monimutkaisuutta. Huomaa ensin, että koska δi ≤ d(Si), δi -ristikon p:n naapuruus sisältää korkeintaan vakiomäärän Si:n pisteitä. Näin ollen kuluu O(log n) aikaa jokaiseen ruudukkoon. Koska tietorakenne sisältää logaritmisen määrän ruudukoita, lisäysalgoritmin ensimmäinen osa vie O(log 2n) aikaa.
Katsotaan algoritmin toista osaa, jossa rakennetaan δj -ruutu. Tämä vaihe vie lajittelun takia O(|Sj |log |Sj|) aikaa. Jos kuitenkin tallennamme pisteet sopivaan lajittelujärjestykseen, tämä ruudukko voidaan rakentaa ajassa O(|Sj|) = O(2j). (Katso lisätietoja.) Koska j voi ottaa minkä tahansa arvon nollan ja ⌊log n⌋ väliltä, lisäämisaika vaihtelee suuresti. Väitämme kuitenkin, että toisen vaiheen kuoletettu aika on rajoitettu O(log n):llä.
Todistaaksemme tämän väitteen oletetaan, että aloitamme tyhjästä joukosta S ja suoritamme n lisäyksen sarjan. Olkoon kj niiden kertojen lukumäärä, jotka näiden lisäysten aikana muodostamme ruudukon osajoukolle, jonka koko on 2j. Tällöin kj on korkeintaan yhtä suuri kuin niiden kokonaislukujen lukumäärä, jotka koostuvat korkeintaan 1 + ⌊log n⌋ bitistä, joiden j vähiten merkitsevää bittiä on yhtä suuri kuin yksi ja joiden (j + 1)-esimmäinen bitti on yhtä suuri kuin nolla. Eli meillä on
Kokonaisaika, joka kuluu toiseen askeleeseen n lisäyksen aikana, on rajoitettu
mikä todistaa väitteen.
Olemme osoittaneet, että koko lähintä paria ylläpitävän algoritmin suoritusaika on rajoitettu O(log 2n) pahimman tapauksen ajalla plus O(log n) amortisoidulla ajalla per lisäys. Käyttämällä tavanomaisia tekniikoita (ks. Overmars ) voimme muuttaa tietorakennetta siten, että toinen vaihe vie pahimmassa tapauksessa logaritmisen ajan. Näin ollen meillä on tietorakenne, joka ylläpitää lähintä paria O(log 2n) pahimman tapauksen ajassa per lisäys. Rakenteen koko on O(n).
Huomaa, että algoritmin ensimmäinen vaihe vie O(log 2n) aikaa, kun taas toinen vaihe vie vain O(log n) aikaa. Tämä viittaa siihen, että parannus on mahdollinen. Sen sijaan, että kirjoittaisimme n:n binäärilukujärjestelmässä, käytämme nimittäin lukujärjestelmää, jonka perusta on log n. (Katso Overmars tai Schwarz .) Näin molemmat vaiheet vievät O(log 2n/log log n) aikaa, kun taas käytetty tila pysyy lineaarisena.
Meillä on siis lineaarisen kokoinen tietorakenne, joka ylläpitää lähintä paria O(log2 n /log log n) pahimmassa tapauksessa ajassa per lisäys. Huomaa, että algoritmi käyttää floor-funktiota löytääkseen ruudukon solun, joka sisältää uuden pisteen p. Korvaamalla ruudukko heikennetyllä ruudukolla algoritmi voidaan toteuttaa algebrallisessa laskentapuumallissa.
Yllä olevaa tietorakennetta on vielä mahdollista parantaa. Tarkastellaan jälleen tietorakennetta, joka perustuu n:n esittämiseen binäärilukujärjestelmässä. Tärkein havainto on seuraava: Jos lisäämme pisteen p, niin jokaiselle i:lle, joka on sellainen, että ai = 1, löydämme δi -puun solun, joka sisältää p:n (sekä viereiset solut). Toisin sanoen suoritamme pisteen sijaintikyselyjä logaritmisessa määrässä ruudukoita, mutta aina samalla kyselypisteellä p. Teoksessa Schwarz ja Smid osoitetaan, että murtolukujen kaskadointitekniikkaa voidaan laajentaa siten, että kaikki nämä kyselyt voidaan ratkaista yhdessä O(log n log log n)-ajassa. Pääongelma on se, että meillä on eri kokoisia ruudukkoja. Siksi on otettava käyttöön ruudukon solujen järjestys, joka on ”yhteensopiva” kaikkien näiden kokojen kanssa. Tällaisessa järjestyksessä määritellään. Tämän seurauksena pisteen p paikantaminen kaikissa ruuduissa vie O(log n) vertailua. Koska järjestys on kuitenkin melko monimutkainen, jokainen vertailu vie O(log log n) aikaa. Kaiken kaikkiaan saamme O(n)-kokoisen tietorakenteen, joka säilyttää lähimmän parin O(log n log log n)-kuoletetussa ajassa per lisäys. Huomaa, että tarvitsemme floor-funktiota tätä tulosta varten. Tämä voidaan luultavasti tehdä pahimmassa tapauksessa, mutta yksityiskohdat ovat työläitä. Ei ole selvää, voidaanko ruudukkosolujen järjestys määritellä myös, jos käytämme tavallisten ruudukkojen sijasta heikennettyjä ruudukkoja.
Mainitsemme lopuksi edellä mainitun tietorakenteen laajennuksen. Edellä kuvattu rakenne hyödyntää voimakkaasti sitä, että lisäämme vain pisteitä. Osoittautuu kuitenkin, että rakenne voidaan mukauttaa käsittelemään Dobkinin ja Surin määrittelemiä semi-online-päivityksiä. Päivitysten sarjaa kutsutaan semi-online-päivitykseksi, jos lisäykset ovat on-line – eli ne saapuvat tuntemattomassa järjestyksessä – mutta kun piste lisätään, meille kerrotaan, kuinka monen päivityksen jälkeen lisäyshetkestä se poistetaan. Tätä poistoja koskevaa lisätietoa voidaan käyttää takaamaan, että kun piste poistetaan, se sisältyy aina pienen osajoukon sisältävään ruudukkoon. Koska poiston yhteydessä vähimmäisetäisyys voi kasvaa, tallennamme tietorakenteeseen lisätietoa lähimmän parin päivittämiseksi tehokkaasti. Tällä tavoin saadaan O(n) kokoinen tietorakenne, joka ylläpitää lähintä paria O(log 2n) pahimmassa tapauksessa O(log 2n)-ajassa per semi-online-päivitys. Yksityiskohdat löytyvät Dobkinin, Surin ja Smidin kirjoista.