3.1 Algoritmy založené na logaritmické metodě
První algoritmy jsou založeny na použití Bentleyho logaritmické metody . Tato aplikace se poprvé objevila ve Smidovi . (Viz také Schwarz .)
Nechť S je aktuální množina bodů v ℝD a nechť n označuje její velikost. Zapište n ve dvojkové číselné soustavě n=∑i≥0ai2i, kde ai ∈ {0,1}. Rozdělte S (libovolně) na podmnožiny: pro každé i takové, že ai = 1, existuje jedna podmnožina Si o velikosti 2i. Navíc pro každé takové i existuje reálné číslo δi takové, že d(S) ≤ δi ≤ d (Si) datová struktura se skládá z následujícího:
(1)
Nejbližší dvojice S a její vzdálenost δ
(2)
Pro každé i takové, že ai = 1, δi -mřížka uchovávající body Si. Předpokládáme, že neprázdné buňky této mřížky jsou uloženy ve vyváženém binárním vyhledávacím stromu, seřazeném lexikograficky podle svých „levých dolních“ rohů.
Nyní uvažujeme vložení nového bodu p. Pro každé i takové, že ai = 1, najdeme buňku δi-mřížky, která obsahuje p spolu s 3D – 1 sousedními buňkami. Poté vypočítáme vzdálenosti mezi bodem p a všemi body Si, které jsou v těchto buňkách obsaženy. Pokud najdeme vzdálenost menší než δ, aktualizujeme δ a nejbližší dvojici. Zbývá aktualizovat zbytek datové struktury. Nechť j je index takový, že a0 = a1 = … = aj – 1 a aj = 0. Nechť Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 a δj := δ. Sestavíme mřížku δj pro množinu Sj a mřížky pro množiny S0, S1,… Sj – 1 zahodíme (čímž tyto množiny implicitně učiníme prázdnými).
Pro důkaz správnosti tohoto algoritmu si všimněte, že jelikož d(S) ≤ δi, stačí porovnat p se všemi body Si, které jsou v sousedství p – v mřížce δi. Nejbližší dvojice je tedy aktualizována správně. Také nová hodnota Sj splňuje d(S ∪ {p}) ≤ δj ≤ d(Sj) a pro všechna i > j máme d(S ∪ {p} ≤ δi d(Si). Nakonec aktualizovaná datová struktura obsahuje mřížku uchovávající 2i bodů pro každé i tak, že binární reprezentace n + 1 obsahuje jedničku na pozici i.
Analyzujeme složitost vkládacího algoritmu. Nejprve si všimněte, že jelikož δi ≤ d(Si), okolí p v mřížce δi obsahuje nejvýše konstantní počet bodů Si. Proto pro každou mřížku spotřebujeme O(log n) času. Protože datová struktura obsahuje logaritmický počet mřížek, zabere první část vkládacího algoritmu O(log 2n) času.
Uvažujme druhou část algoritmu, ve které sestavujeme δj -mřížku. Tento krok zabere O(|Sj |log |Sj|) času kvůli třídění. Pokud však uložíme body ve vhodném setříděném pořadí, pak lze tuto mřížku sestavit v čase O(|Sj|) = O(2j). (Protože j může nabývat libovolné hodnoty mezi nulou a ⌊log n⌋, doba vkládání značně kolísá. Tvrdíme však, že amortizovaný čas druhého kroku je omezen hodnotou O(log n).
Pro důkaz tohoto tvrzení předpokládejme, že začneme s prázdnou množinou S a provedeme posloupnost n vložení. Nechť kj je počet případů, kdy během těchto vložení sestavíme mřížku pro podmnožinu velikosti 2j Pak kj je nejvýše rovno počtu celých čísel složených nejvýše z 1 + ⌊log n⌋ bitů, jejichž j nejméně významných bitů je rovno jedné a jejichž (j + 1)-stý bit je roven nule. To znamená, že máme
Celkový čas strávený pro druhý krok během n vložení je omezen
což dokazuje tvrzení.
Ukázali jsme, že doba běhu celého algoritmu pro udržení nejbližší dvojice je omezena časem O(log 2n) v nejhorším případě plus O(log n) amortizovaného času na vložení. Pomocí standardních technik (viz Overmars ) můžeme datovou strukturu transformovat tak, aby druhý krok trval v nejhorším případě logaritmický čas. Máme tedy datovou strukturu, která udržuje nejbližší dvojici v nejhorším případě v čase O(log 2n) na jedno vložení. Struktura má velikost O(n).
Všimněte si, že první krok algoritmu trvá O(log 2n) času, zatímco druhý krok trvá pouze O(log n) času. To naznačuje, že zlepšení je možné. Místo zápisu n ve dvojkové číselné soustavě totiž použijeme číselnou soustavu se základem log n. (Viz Overmars nebo Schwarz .) Tímto způsobem oba kroky zaberou O(log 2n/log log n) času, zatímco použitý prostor zůstává lineární.
Máme tedy datovou strukturu lineární velikosti, která udržuje nejbližší dvojici v nejhorším případě O(log2 n /log log n) času na vložení. Všimněte si, že algoritmus používá funkci floor k nalezení buňky mřížky obsahující nový bod p. Nahrazením mřížky degradovanou mřížkou lze algoritmus implementovat v modelu algebraického výpočetního stromu.
Výše uvedenou datovou strukturu lze ještě vylepšit. Uvažujme opět datovou strukturu založenou na reprezentaci n ve dvojkové číselné soustavě. Hlavní postřeh je následující: Pokud vložíme bod p, pak pro každé i takové, že ai = 1, najdeme buňku δi -stromu, která obsahuje p (plus sousední buňky). To znamená, že provádíme dotazy na umístění bodu v logaritmickém počtu mřížek, ale vždy se stejným dotazovaným bodem p. Ve Schwarzovi a Šmídovi je ukázáno, že zlomkovou kaskádovou techniku lze rozšířit tak, že všechny tyto dotazy dohromady lze vyřešit v čase O(log n log n). Hlavní problém spočívá v tom, že máme mřížky o různých velikostech. Proto je třeba zavést uspořádání buněk mřížky, které je „kompatibilní“ se všemi těmito velikostmi. V takovém uspořádání je definováno. Výsledkem je, že nalezení bodu p ve všech mřížkách trvá O(log n) porovnání. Protože je však toto uspořádání poměrně složité, trvá každé porovnání O(log log n) času. Celkově dostaneme datovou strukturu o velikosti O(n), která udržuje nejbližší dvojici v amortizovaném čase O(log n log n) na jedno vložení. Všimněte si, že pro tento výsledek potřebujeme funkci floor. Pravděpodobně to lze provést v nejhorším případě, ale detaily budou zdlouhavé. Není jasné, zda lze definovat i uspořádání na buňkách mřížky, pokud místo standardní mřížky použijeme degradovanou mřížku.
Nakonec se zmíníme o rozšíření výše uvedené datové struktury. Výše popsaná struktura silně využívá toho, že vkládáme pouze body. Ukazuje se však, že strukturu lze přizpůsobit pro práci s polopřímými aktualizacemi, jak je definovali Dobkin a Suri . Posloupnost aktualizací se nazývá semi-online, pokud jsou vložení on-line – tj. přicházejí v neznámém pořadí – ale když je bod vložen, je nám řečeno, po kolika aktualizacích od okamžiku vložení bude vymazán. Tuto dodatečnou informaci o výmazech lze využít k tomu, aby bylo zaručeno, že když je bod vymazán, je vždy obsažen v mřížce uchovávající malou podmnožinu. Protože při vymazání může minimální vzdálenost vzrůst, ukládáme do datové struktury další informace pro efektivní aktualizaci nejbližší dvojice. Tímto způsobem získáme datovou strukturu o velikosti O(n), která udržuje nejbližší dvojici v nejhorším případě v čase O(log 2n) na jednu semi-online aktualizaci. Pro podrobnosti odkazujeme čtenáře na Dobkina a Suriho a Šmída .