3.1 Logaritmikus módszerre épülő algoritmusok
Az első algoritmusok Bentley logaritmikus módszerének alkalmazásán alapulnak. Ez az alkalmazás először Smidnél jelent meg . (Lásd még Schwarz .)
Legyen S az ℝD aktuális ponthalmaza, és jelölje n a méretét. Írjuk n-t a bináris számrendszerben: n=∑i≥0ai2i, ahol ai ∈ {0,1}. Osszuk S-t (tetszőlegesen) részhalmazokra: minden olyan i-re, hogy ai = 1, van egy Si részhalmaz, amelynek mérete 2i. Továbbá minden ilyen i-re van egy olyan δi valós szám, hogy d(S) ≤ δi ≤ d (Si) az adatszerkezet a következőkből áll.
(1)
Az S legközelebbi párja és annak távolsága δ
(2)
Minden olyan i-re, hogy ai = 1, egy δi -rács, amely az Si pontjait tárolja. Feltételezzük, hogy e rács nem üres celláit egy kiegyensúlyozott bináris keresőfában tároljuk, “bal alsó” sarkuk szerint lexikográfiailag rendezve.
Most tekintsük egy új p pont beszúrását. Minden olyan i-re, hogy ai = 1, megkeressük a δi-rács azon celláját, amely a p-t tartalmazza a 3D – 1 szomszédos cellákkal együtt. Ezután kiszámítjuk a p és az Si összes olyan pontja közötti távolságokat, amelyek ezekben a cellákban szerepelnek. Ha δ-nél kisebb távolságot találunk, akkor frissítjük δ-t, és a legközelebbi párt. Már csak az adatszerkezet többi részének frissítése van hátra. Legyen j egy olyan index, hogy a0 = a1 = … = aj – 1 és aj = 0. Legyen Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 és δj := δ. Az Sj halmazra egy δj -rácsot építünk, és az S0, S1, … Sj – 1 halmazra vonatkozó rácsokat elvetjük (ezzel implicit módon üressé tesszük ezeket a halmazokat).
Az algoritmus helyességének bizonyításához megjegyezzük, hogy mivel d(S) ≤ δi, elegendő p-t összehasonlítani Si minden olyan pontjával, amely p szomszédságában van – a δi-rácsban. Ennélfogva a legközelebbi pár helyesen frissül. Továbbá az új Sj érték kielégíti a d(S ∪ {p}) ≤ δj ≤ d(Sj), és minden i > j esetén d(S ∪ {p} ≤ δi d(Si). Végül a frissített adatszerkezet minden i-hez tartalmaz egy 2i pontot tároló rácsot úgy, hogy az n + 1 bináris ábrázolása az i pozícióban egy egyest tartalmazzon.
Elemezzük a beszúrási algoritmus bonyolultságát. Először is megjegyezzük, hogy mivel δi ≤ d(Si), a p szomszédsága a δi -rácsban legfeljebb állandó számú Si pontot tartalmaz. Ezért minden egyes rácsra O(log n) időt fordítunk. Mivel az adatszerkezet logaritmikusan sok rácsot tartalmaz, a beszúrási algoritmus első része O(log 2n) időt vesz igénybe.
Lássuk az algoritmus második részét, amelyben felépítjük a δj -rácsot. Ez a lépés a rendezés miatt O(|Sj |log |Sj|) időt vesz igénybe. Ha azonban a pontokat megfelelő rendezésben tároljuk, akkor ez a rács O(|Sj|) = O(2j) idő alatt felépíthető. (Lásd a részleteket.) Mivel j bármilyen értéket felvehet nulla és ⌊log n⌋ között, a beillesztési idő nagymértékben ingadozik. Azt állítjuk azonban, hogy a második lépés amortizált ideje O(log n) által korlátozott.
Az állítás bizonyításához tegyük fel, hogy egy üres S halmazzal kezdünk, és egy n beillesztésből álló sorozatot hajtunk végre. Legyen kj azon esetek száma, amikor e beszúrások során egy 2j méretű részhalmazra rácsot építünk Akkor kj legfeljebb annyi, mint azon egész számok száma, amelyek legfeljebb 1 + ⌊log n⌋ bitekből állnak, amelyek j legkevésbé jelentős bitje egyenlő eggyel, és amelyek (j + 1)-edik bitje egyenlő nullával. Vagyis van
A második lépésre fordított teljes idő az n beszúrás során
mely bizonyítja az állítást.
Bebizonyítottuk, hogy a legközelebbi pár fenntartására szolgáló teljes algoritmus futási ideje O(log 2n) legrosszabb esetű idővel plusz O(log n) beillesztésenkénti amortizált idővel korlátozott. A szokásos technikák alkalmazásával (lásd Overmars ) úgy alakíthatjuk át az adatszerkezetet, hogy a második lépés legrosszabb esetben logaritmikus időt vegyen igénybe. Így olyan adatszerkezetünk van, amely beillesztésenként O(log 2n) legrosszabb esetben O(log 2n) idő alatt tartja fenn a legközelebbi párt. A struktúra mérete O(n).
Megjegyezzük, hogy az algoritmus első lépése O(log 2n) időt vesz igénybe, míg a második lépés csak O(log n) időt. Ez arra utal, hogy lehetséges a javítás. Valóban, ahelyett, hogy n-t bináris számrendszerben írnánk, használjuk a log n bázisú számrendszert. (Lásd Overmars vagy Schwarz .) Így mindkét lépés O(log 2n/log log n) időt vesz igénybe, miközben a felhasznált hely lineáris marad.
Ezért van egy lineáris méretű adatszerkezetünk, amely beillesztésenként O(log2 n /log log n) legrosszabb esetben O(log2 n /log log n) idő alatt tartja fenn a legközelebbi párt. Megjegyezzük, hogy az algoritmus a floor függvényt használja az új p pontot tartalmazó rácscella megtalálásához.
A rácsot egy degradált ráccsal helyettesítve az algoritmus megvalósítható az algebrai számítási fa modellben.
A fenti adatszerkezetet még lehet javítani. Tekintsük ismét az n bináris számrendszerben való ábrázolásán alapuló adatszerkezetet. A fő megfigyelés a következő: Ha beillesztünk egy p pontot, akkor minden olyan i-re, hogy ai = 1, megkeressük a δi -fa azon celláját, amely tartalmazza p-t (plusz a szomszédos cellákat). Vagyis logaritmikusan sok rácsban végzünk pontmeghatározási lekérdezéseket, de mindig ugyanazzal a p lekérdezési ponttal. Schwarz és Smid cikkében megmutatja, hogy a tört kaszkádos technika kiterjeszthető úgy, hogy az összes ilyen lekérdezés együtt O(log n log log n) idő alatt megoldható. A fő probléma az, hogy különböző rácsméretű rácshálóink vannak. Ezért olyan rendezést kell bevezetni a rácscellákra, amely “kompatibilis” mindezekkel a méretekkel. Egy ilyen rendezést definiálunk. Ennek eredményeképpen a p pont megtalálása minden rácson O(log n) összehasonlítást vesz igénybe. Mivel azonban a rendezés meglehetősen bonyolult, minden egyes összehasonlítás O(log log n) időt vesz igénybe. Összességében egy O(n) méretű adatszerkezetet kapunk, amely beillesztésenként O(log n log log n) amortizált idő alatt tartja fenn a legközelebbi párt. Megjegyezzük, hogy ehhez az eredményhez szükségünk van a floor függvényre. Ez valószínűleg a legrosszabb esetben is megvalósítható, de a részletek kidolgozása fárasztó lesz. Nem világos, hogy a rácscellákon való rendezés akkor is meghatározható-e, ha normál rácsok helyett degradált rácsokat használunk.
Végezetül megemlítjük a fenti adatszerkezet egy kiterjesztését. A fent leírt struktúra erősen kihasználja, hogy csak pontokat illesztünk be. Kiderül azonban, hogy a struktúra adaptálható a Dobkin és Suri által definiált félig online frissítések kezelésére. A frissítések sorozatát félig-vonalasnak nevezzük, ha a behelyezések on-line történnek – azaz ismeretlen sorrendben érkeznek -, de amikor egy pontot behelyezünk, tudjuk, hogy a behelyezéstől számított hányadik frissítés után fogjuk törölni. Ez a törlésekre vonatkozó többletinformáció felhasználható annak garantálására, hogy amikor egy pontot törölünk, az mindig egy kis részhalmazt tároló rácsban szerepeljen. Mivel törléskor a minimális távolság növekedhet, a legközelebbi pár hatékony frissítése érdekében extra információt tárolunk az adatstruktúrában. Így egy O(n) méretű adatszerkezetet kapunk, amely a legközelebbi párt O(log 2n) legrosszabb esetben O(log 2n) idő alatt tartja fenn félig online frissítésenként. A részletekért az olvasót Dobkin és Suri, valamint Smid .
című munkájához ajánljuk.