Kinetická šířka - Kinetic width

A kinetická šířka datová struktura je a kinetická datová struktura který udržuje šířka sady pohyblivých bodů. Ve 2D je šířka sady bodů minimální vzdálenost mezi dvěma rovnoběžnými čarami, které obsahují sadu bodů v pásu mezi nimi. Pro dvourozměrný případ je struktura kinetických dat pro kinetický konvexní trup lze použít ke konstrukci kinetické datové struktury pro šířku množiny bodů, která je citlivý, kompaktní a účinný.

2D pouzdro

Vezměme si rovnoběžky, které obsahují bod nastavený v pásu mezi nimi a jsou od sebe vzdáleny minimálně. Jeden z řádků musí obsahovat hranu ${ displaystyle ab}$ konvexního trupu a druhá čára musí projít bodem c konvexního trupu tak, aby (a, c) a (b, c) byly antipodální páry. ab a c jsou označovány jako antipodální pár hrana-vrchol. Zvažte dvojí množiny bodů. Body se zdvojnásobí na čáry a konvexní trup bodů se dualizuje na horní a dolní obálku sady čar. Vrcholy horního konvexního trupu se zdvojnásobí na segmenty na horní obálce. Vrcholy dolního konvexního trupu se zdvojnásobí na segmenty na spodní obálce. Rozsah svahů nosných linií bodu na trupu se zdvojnásobí na x-interval segmentu, do kterého se tento bod dualizuje. Při pohledu tímto dualizovaným způsobem jsou antipodální páry páry segmentů, jeden z horní obálky, druhý ze spodní, s překrývajícími se x rozsahy. Nyní lze horní a dolní obálku zobrazit jako dva různé seznamy nepřekrývajících se intervalů seřazené podle x. Pokud jsou tyto dva seznamy sloučeny, antipodální páry jsou přesahy ve sloučeném seznamu. Pokud pár ${ displaystyle ab}$ a c je antipodální pár hrana-vrchol, pak x-interval pro a a b musí oba protínat x-interval pro c. To znamená, že společný koncový bod intervalů x pro a a b musí ležet v intervalu x pro c.

Koncové body obou sad intervalů x lze udržovat v a kinetický seřazený seznam. Když se body vymění, seznam dvojic protilehlých hranových bodů se odpovídajícím způsobem aktualizuje. Horní a dolní obálky lze udržovat pomocí standardní datové struktury pro kinetický konvexní trup. Minimální vzdálenost mezi páry okrajových bodů může být udržována pomocí a kinetický turnaj. Takže pomocí kinetického konvexního trupu k udržení horní a dolní obálky, kinetického seřazeného seznamu v těchto intervalech k udržení antipodálních párů hrana-vrchol a kinetického turnaje k udržení dvojice minimální vzdálenosti od sebe, je průměr pohybujícího se bodu nastaven lze udržovat.

Tato datová struktura je citlivý, kompaktní a účinný. Datová struktura používá ${ displaystyle O (n)}$ prostor, protože to vše využívá kinetický konvexní trup, seřazený seznam a datové struktury turnaje ${ displaystyle O (n)}$ prostor. Ve všech datových strukturách lze zpracovávat události, vložky a mazání ${ displaystyle O ( log ^ {2} n)}$ času, takže datová struktura reaguje a vyžaduje ${ displaystyle O ( log ^ {2} n)}$ na událost. Datová struktura je efektivní, protože celkový počet událostí je ${ displaystyle O (n ^ {2+ epsilon})}$ pro všechny ${ displaystyle epsilon> 0}$ a šířka množiny bodů se může změnit ${ displaystyle Omega (n ^ {2})}$ krát, i když se body pohybují lineárně. Tato datová struktura není místní protože jeden bod může být v mnoha antipodálních párech hrana-vrchol, a tak se mnohokrát objeví v kinetickém turnaji.

Existence lokální kinetické datové struktury pro šířku je otevřená.

Vyšší rozměry

Efektivní udržování kinetické šířky bodu nastaveného v dimenzích vyšších než 2 je otevřeným problémem. Účinný kinetický konvexní trup v dimenzích vyšších než 2 je také otevřený problém.^[1]

Související problémy

Reference

^ 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-1584884354

Další čtení

P. K. Agarwal, L. J. Guibas, J. Hershberger a E. Verach. Udržování rozsahu pohybující se sady bodů.

[1] 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-1584884354

[1]