Kinetický nejmenší uzavírací disk - Kinetic smallest enclosing disk

A kinetický nejmenší uzavírací disk datová struktura je a kinetická datová struktura který udržuje nejmenší uzavírací disk sady pohyblivých bodů.

2D

Ve 2 dimenzích používá nejznámější kinetická nejmenší datová struktura uzavírajícího disku nejvzdálenější delaunayskou triangulaci bodové sady k udržení nejmenší uzavírajícího disku.^[1] Nejvzdálenější bod Delaunayova triangulace je dvojí z nejvzdálenější Voronoiův diagram. Je známo, že pokud nejdelší delaunayova triangulace bodové sady obsahuje akutní trojúhelník, je obvod tohoto trojúhelníku je nejmenší obklopující disk. Jinak má nejmenší uzavírací disk průměr bodu nastaveného jako jeho průměr. Tím, že udržuje kinetický průměr množiny bodů, nejvzdálenější delaunayova triangulace a bez ohledu na to, zda nejvzdálenější delaunayská triangulace má akutní trojúhelník, lze zachovat nejmenší uzavírací disk. Tato datová struktura je responzivní a kompaktní, ale není lokální ani efektivní:^[1]

• Schopnost reagovat: Tato datová struktura vyžaduje ${ displaystyle O ( log ^ {2} n)}$ čas na zpracování každého selhání certifikátu, a proto reaguje.
• Lokalita: Bod může být zapojen do ${ displaystyle Theta (n)}$ certifikáty. Proto tato datová struktura není místní.
• Kompaktnost: Tato datová struktura vyžaduje celkem O (n) certifikátů, a proto je kompaktní.
• Účinnost: Tato datová struktura má ${ displaystyle O (n ^ {3+ epsilon})}$ události celkem. (pro všechny ${ displaystyle epsilon> 0}$ Nejznámější dolní mez počtu změn nejmenšího uzavíracího disku je ${ displaystyle Omega (n ^ {2})}$. Účinnost této datové struktury, tedy poměr celkových událostí k vnějším, je tedy ${ displaystyle O (n ^ {1+ epsilon})}$.

Existence kinetické datové struktury, která má ${ displaystyle o (n ^ {3+ epsilon})}$ událostí je otevřený problém.^[1]

Přibližně 2D

Nejmenší uzavírací disk ze sady n pohyblivých bodů může být ε-aproximováno kinetickou datovou strukturou, která zpracovává ${ displaystyle O (1 / epsilon ^ {5/2})}$ události a vyžaduje ${ displaystyle O ((n / { sqrt { epsilon}}) log n)}$ celkový čas.^[2]

Vyšší rozměry

V dimenzích vyšších než 2 je efektivní udržování nejmenší obklopující koule sady pohyblivých bodů otevřeným problémem.^[1]

Reference