Kinetická datová struktura - Kinetic data structure - Wikipedia

A kinetická datová struktura je datová struktura slouží ke sledování atributu geometrického systému, který se neustále pohybuje.^[1]^[2]^[3]^[4]Například a kinetický konvexní trup datová struktura udržuje konvexní trup skupiny ${ displaystyle n}$ pohyblivé body. Vývoj kinetických datových struktur byl motivován výpočetní geometrie problémy spojené s fyzickými objekty v nepřetržitém pohybu, jako je například kolize nebo detekce viditelnosti v robotice, animaci nebo počítačové grafice.

Přehled

Kinetické datové struktury se používají v systémech, kde existuje sada hodnot, které se známým způsobem mění jako funkce času. Takže systém má nějaké hodnoty a pro každou hodnotu ${ displaystyle v}$ , je známo že ${ displaystyle v = f (t)}$ Kinetické datové struktury umožňují dotazy v systému v aktuálním virtuálním čase ${ displaystyle t}$ a dvě další operace:

${ displaystyle { textrm {advance}} (t)}$ : Postupuje systém časem ${ displaystyle t}$ .
${ displaystyle { textrm {změnit}} (v, f (t))}$ : Mění trajektorii hodnoty ${ displaystyle v}$ na ${ displaystyle f (t)}$ , aktuálního času.

Mohou být podporovány další operace. Například kinetické datové struktury se často používají se sadou bodů. V tomto případě struktura obvykle umožňuje vkládání a mazání bodů.

Kontrast s tradičními datovými strukturami

Kinetická datová struktura umožňuje, aby se v ní uložené hodnoty neustále měnily s časem. V zásadě to lze aproximovat vzorkováním polohy bodů ve stanovených časových intervalech a odstraněním a opětovným vložením každého bodu do „statické“ (tradiční) datové struktury. Takový přístup je však citlivý na převzorkování nebo podvzorkování v závislosti na použitém časovém intervalu a může také plýtvat výpočetními zdroji.

Přístup k certifikátům

Ke konstrukci kinetických datových struktur lze použít následující obecný přístup:^[5]

Uložte datovou strukturu v systému v aktuálním čase ${ displaystyle t}$ . Tato datová struktura umožňuje dotazy na systém v aktuálním virtuálním čase.
Rozšiřte datovou strukturu o certifikáty. Certifikáty jsou podmínky, za kterých je datová struktura přesná. Všechny certifikáty jsou nyní pravdivé a datová struktura přestane být přesná, až když jeden z certifikátů přestane platit.
Vypočítejte dobu selhání každého certifikátu, čas, kdy přestane platit.
Uložte certifikáty do prioritní fronty s klíčem podle doby jejich selhání
Postupovat včas ${ displaystyle t}$ , podívejte se na certifikát s nejnižší dobou selhání z prioritní fronty. Pokud certifikát selže před časem ${ displaystyle t}$ , vyjměte ji z fronty a opravte datovou strukturu, aby byla přesná v době selhání, a aktualizujte certifikáty. Opakujte to, dokud certifikát s nejnižší dobou selhání ve frontě priorit po určité době selže ${ displaystyle t}$ . Pokud certifikát s nejnižší dobou selhání v prioritní frontě po čase selže ${ displaystyle t}$ , pak jsou všechny certifikáty platné současně ${ displaystyle t}$ takže datová struktura může správně odpovídat na dotazy v čase ${ displaystyle t}$ .

Druhy událostí

Selhání certifikátu se označují jako „události“. Událost je považována za interní, pokud se vlastnost udržovaná strukturou kinetických dat při výskytu události nezmění. Událost je považována za externí, pokud se vlastnost udržovaná datovou strukturou změní, když k události dojde.

Výkon

Při použití přístupu certifikátů existují čtyři měřítka výkonu. Říkáme, že množství je malé, pokud je polylogaritmická funkce z ${ displaystyle n}$ , nebo je ${ displaystyle O (n ^ { epsilon})}$ pro libovolně malé ${ displaystyle epsilon}$ , kde ${ displaystyle n}$ je počet objektů:

Schopnost reagovat

Schopnost reagovat je nejhorším případem množství času potřebného k opravě datové struktury a rozšíření certifikátů, když certifikát selže. Kinetická datová struktura reaguje, pokud je nejhorší doba potřebná k aktualizaci malá.

Lokalita

Maximální počet certifikátů, do kterých je zahrnuta jedna hodnota. U struktur zahrnujících pohyblivé body je to maximální počet certifikátů, do kterých je zahrnut jeden bod. Kinetická datová struktura je lokální, pokud je zahrnut maximální počet certifikátů, u kterých je jedna hodnota zahrnuta je malý.

Kompaktnost

Maximální počet certifikátů použitých k rozšíření datové struktury kdykoli. Kinetická datová struktura je kompaktní, pokud je počet použitých certifikátů ${ displaystyle O (n operatorname {polylog} n)}$ nebo ${ displaystyle O (n ^ {1+ epsilon})}$ pro libovolně malé ${ displaystyle epsilon}$ . (malý faktor více než lineární prostor)

Účinnost

Poměr počtu nejhorších případů, ke kterému může dojít, když je struktura postoupena ${ displaystyle t = infty}$ v nejhorším případě počet „nezbytných změn“ datové struktury. Definice „nezbytných změn“ závisí na problému. Například v případě, že kinetická datová struktura udržuje kinetický trup sady pohybujících se bodů, počet potřebných změn by byl počet, kolikrát se kinetický trup mění s postupujícím časem ${ displaystyle t = infty}$ . Kinetická datová struktura je považována za efektivní, pokud je tento poměr malý.

Druhy trajektorií

Výkon určité struktury kinetických dat lze analyzovat pro určité typy trajektorií. Obvykle se uvažují následující typy trajektorií:

Afinní: (Lineární funkce) ${ displaystyle f (t) = v + b}$
Ohraničený stupeň algebraiky: (Polynomiální funkce omezeného stupně) ${ displaystyle f (t) = součet _ {i = 0} ^ {n} a_ {i} t ^ {i}}$ pro některé pevné ${ displaystyle n}$ .
Pseudoalgebraické: Trajektorie takové, že jakýkoli certifikát zájmu se otáčí mezi pravdivým a nepravdivým ${ displaystyle O (1)}$ krát.

Příklady

Reference

^ Basch, Julien (1999). Kinetické datové struktury (Teze). Stanfordská Univerzita.
^ Guibas, Leonidas J. (2001), „Kinetické datové struktury“ (PDF), Mehta, Dinesh P .; Sahni, Sartaj (eds.), Příručka datových struktur a aplikací, Chapman and Hall / CRC, s. 23-1–23-18, ISBN 978-1-58488-435-4
^ Abam, Mohammad Ali (2007). Nové datové struktury a algoritmy pro mobilní data (Teze). Eindhoven University of Technology.
^ Rahmati, Zahed (2014). Jednoduché a rychlejší kinetické datové struktury (Teze). University of Victoria. hdl:1828/5627.
^ Guibas, Leonidas J. (1998), „Kinetické datové struktury: zpráva o stavu techniky“ (PDF), Agarwal, Pankaj K .; Kavraki, Lydia E .; Mason, Matthew T. (eds.), Robotics: The Algorithmic Perspective (Proceedings of the 3rd Workshop on the Algorithmic Foundations of Robotics), A K Peters / CRC Press, s. 191–209, ISBN 978-1-56881-081-2

externí odkazy

[JBasch-1] Basch, Julien (1999). Kinetické datové struktury (Teze). Stanfordská Univerzita.

[LJGuibas-2] Guibas, Leonidas J. (2001), „Kinetické datové struktury“ (PDF), Mehta, Dinesh P .; Sahni, Sartaj (eds.), Příručka datových struktur a aplikací, Chapman and Hall / CRC, s. 23-1–23-18, ISBN 978-1-58488-435-4

[MAAbam-3] Abam, Mohammad Ali (2007). Nové datové struktury a algoritmy pro mobilní data (Teze). Eindhoven University of Technology.

[ZRahmati-4] Rahmati, Zahed (2014). Jednoduché a rychlejší kinetické datové struktury (Teze). University of Victoria. hdl:1828/5627.

[5] Guibas, Leonidas J. (1998), „Kinetické datové struktury: zpráva o stavu techniky“ (PDF), Agarwal, Pankaj K .; Kavraki, Lydia E .; Mason, Matthew T. (eds.), Robotics: The Algorithmic Perspective (Proceedings of the 3rd Workshop on the Algorithmic Foundations of Robotics), A K Peters / CRC Press, s. 191–209, ISBN 978-1-56881-081-2

[1]

[2]

[3]

[4]

[5]