Kinetický nejbližší pár - Kinetic closest pair - Wikipedia
A kinetický nejbližší pár datová struktura je a kinetická datová struktura který udržuje nejbližší dvojice bodů, vzhledem k sadě P z n body, které se v metrickém prostoru pohybují nepřetržitě s časem. Zatímco mnoho účinný algoritmy byly známy ve statickém případě, ukázalo se to těžké kinetizovat,[1] k vyřešení tohoto problému byly vyvinuty nové statické algoritmy.
2D pouzdro
Přístup 1
Nejjednodušší kinetický přístup pro údržbu nejbližšího páru je použití variant Delaunayovy triangulace.[2]
Zvažte šestiúhelník a rozdělte jej na šest rovnostranné trojúhelníky, a poté vytvořte Delaunayovu triangulaci založenou na každém rovnostranném trojúhelníku, protože každý z nich má konvexní tvar. Spojení těchto šesti Delaunayových triangulací, tzv. Rovnostranný Delaunayův graf (EDG), je supergrafem pro graf nejbližšího souseda (NNG); koncové body hrany s minimální délkou v EDG dávají nejbližší pár. Je jednoduché udržovat Delaunayovy triangulace založené na konvexních tvarech. Vzhledem k EDG v průběhu času vytvořením kinetický turnajový strom přes okraje EDG lze snadno udržovat nejbližší pár.
Tento nejbližší pár KDS je efektivní, amortizovaný, citlivý a kompaktní, ale obecně není lokální. Následující přístup představuje místní KDS pro údržbu nejbližšího páru.
Přístup 2

Druhý kinetický přístup je založen na následujících pozorováních.[3][4]
Rozděl a panuj
Pokud je prostor kolem bodu p je rozdělena úhlově na šest „klínů“ 60° široký, nejbližší bod p je nejbližší k nejbližším bodům v každém z klínů. Zbytek tohoto článku se zaměří na „hlavní“ klínky (ty, které jsou půlené osou x), a symetrické argumenty se použijí na ostatní klínky po otočení roviny o ±60°.
Shodné body
Body p a q jsou považovány za „uzavřené“, pokud jsou si navzájem nejblíže. Je zřejmé, že nejbližší pár bodů je párový pár.
Zvažte body p a q, takový, že p je nalevo od q a q leží v klínu se středem na p popsáno výše. Li p je nejbližší bod q, pak q musí být nejbližší bod (v tomto klínu) p, ve směru x. Sada dvojic nejbližších bodů (v tomto klínu) ve směru x je tedy nadmnožinou sady párů nejbližších bodů.
Konstrukce
- Zmapujte každý bod p=(X, y) v sadě P do nového bodu p ' = (u, proti) = (x +√3y, y-√3X), tvořící sadu P ' transformovaných bodů. Všimněte si, že pro bod p, body v „hlavních“ klínech mají u a proti souřadnice buď větší, nebo menší než p ' v tomto novém souřadnicovém systému.
- Seřadit body podle X,u a proti souřadnice a uložit je do kinetické seřazené seznamy.
- Vytvořte 2D rozsah strom T na bodech v P '. Pro každý uzel w v primárním stromu, let T(w) být sekundární strom spojený s w. Tento strom rozsahu se použije k identifikaci bodů v „hlavním“ klínu bodu w.
- Pro každý uzel w v primárním stromu a v každém uzlu E v T(w), vypočítat pár π(w, e) = (b, r), kde b (nebo r) je definován jako bod s maximální (nebo minimální) souřadnicí x v levém (nebo pravém) podstromu E. Nechat Π (0) být množinou π(w, e) pro všechny páry w, E v T. Toto je nadmnožina sady párů nejbližších bodů (v hlavním klínu).
- Postavit fronta kinetické priority na párech v Π (0), s prioritami určenými vzdáleností (měřenou v původním souřadném systému) mezi body v páru.
- Výše uvedené kroky opakujte pro rovinu otočenou ±60°, abyste dostali fronty kinetické priority Π (1) a Π (-1) resp.
Nejbližší pár bodů v P odpovídá minimu minim získaných ze tří prioritních front Π výše.
Údržba
K selhání certifikátu může dojít ve frontách priorit a seřazených seznamech. Výměny v pořadí bodů způsobí změny T (což bude trvat O (log2 n) času) a může způsobit vložení / smazání v prioritních frontách.
Všimněte si, že počet změn sad Π jak je definováno výše, nemusí to být konstantní číslo. Jakýkoli pár, který začne nebo přestane odpovídat v důsledku řazení změn p a q, však musí obsahovat p a / nebo q, a proto existuje pouze konstantní počet párovaných párů, které musí být vloženy do / odstraněny z priority fronty. Je v pořádku aktualizovat pouze tyto párované páry, protože podle definice pouze párované páry mají šanci být nejbližším párem.
Analýza
Tato KDS je:
- Reagovat: bere O (log2 n) čas na zpracování události
- Místní: protože každý bod je přítomen ve stálém počtu kineticky seřazených seznamů a front kinetických priorit, vychází lokalita z lokality těchto struktur
- Kompaktnost: kompaktnost vyplývá z kompaktnosti kineticky seřazených seznamů a front kinetické priority
- Účinný: každý swap v seřazených seznamech způsobí konstantní počet vkládání a mazání ve frontách kinetické priority. Za předpokladu, že pohyb bodů je pseudoalgebraický, existuje polynomiální počet swapů, a proto je tento KDS zpracován polynomický počet událostí, což je efektivní
Tento přístup lze použít k udržení nejbližšího páru ve vyšších dimenzích.
Reference
- ^ Basch, J., Guibas, L. J., Hershberger, J (1997). "Datové struktury pro mobilní data". Sborník příspěvků z osmého ročníku sympozia ACM-SIAM o diskrétních algoritmech. SODA. Společnost pro průmyslovou a aplikovanou matematiku. 747–756. Citováno 17. května 2012.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Rahmati, Z .; King, V.; Whitesides, S. (2013). Kinetické datové struktury pro všechny nejbližší sousedy a nejbližší pár v rovině. Sborník 29. sympozia ACM o výpočetní geometrii. s. 137–144. doi:10.1145/2462356.2462378.
- ^ Basch, Julien; Guibas, Leonidas J .; Zhang, Li (1997). Problémy s blízkostí v pohyblivých bodech. Sborník 13. sympozia ACM o výpočetní geometrii. str. 344–351.
- ^ Agarwal, P.K .; Kaplan, Haim; Sharir, Micha (listopad 2008). „Kinetické a dynamické datové struktury pro nejbližší pár a všechny nejbližší sousedy“. Transakce na algoritmech (TALG). 5 (1).