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

Kinetická nejbližší dvojice preliminaries.png

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

  1. 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.
  2. Seřadit body podle X,u a proti souřadnice a uložit je do kinetické seřazené seznamy.
  3. 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.
  4. 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).
  5. 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.
  6. 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

  1. ^ 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)
  2. ^ 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.
  3. ^ 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.
  4. ^ 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).