Kinetisk triangulering

En kinetisk trianguleringsdatastruktur är en kinetisk datastruktur som upprätthåller en triangulering av en uppsättning rörliga punkter. Att upprätthålla en kinetisk triangulering är viktigt för applikationer som involverar rörelseplanering , såsom videospel, virtuell verklighet, dynamiska simuleringar och robotik.

Att välja ett trianguleringsschema

Effektiviteten hos en kinetisk datastruktur definieras baserat på förhållandet mellan antalet interna händelser och externa händelser, så bra körtidsgränser kan ibland erhållas genom att välja att använda ett trianguleringsschema som genererar ett litet antal externa händelser. För enkel affin rörelse av punkterna uppskattas antalet diskreta förändringar av det konvexa skrovet med $\Omega (n^{2})$ , således är antalet ändringar av varje triangulering också lägre avgränsad av $\Omega (n^{2})$ . Att hitta ett trianguleringsschema som har en nästan kvadratisk gräns för antalet diskreta förändringar är ett viktigt öppet problem.

Delaunay triangulering

Delaunay -trianguleringen verkar vara en naturlig kandidat, men en noggrann värsta-fallsanalys av antalet diskreta förändringar som kommer att inträffa i Delaunay-trianguleringen (externa händelser) ansågs vara ett öppet problem fram till 2015; den har nu avgränsats till att vara mellan $\Omega (n^{2})$ och $O(n^{2+\epsilon })$ .

Det finns en kinetisk datastruktur som effektivt upprätthåller Delaunay-trianguleringen $) {\displaystyle O(1)}$ en uppsättning rörliga punkter, där förhållandet mellan det totala antalet händelser och antalet externa händelser är .

Andra trianguleringar

Kaplan et al. utvecklat ett randomiserat trianguleringsschema som upplever ett förväntat antal $O(n^{2}\beta _{s+2}(n)\log ^{2}n)$ externa händelser, där $s$ är det maximala antalet gånger varje trippel av punkter kan bli kolinjär, ${\displaystyle \beta _{s+2}(q)={\frac {\lambda _{s+2}(q)}{q}}} och λ s + 2 (q$ ) $s +2}(q)}$ är den maximala längden av en Davenport-Schinzel-sekvens av ordningen s + 2 på n symboler.

Pseudo-triangulering

Det finns en kinetisk datastruktur (beroende på Agarwal et al.) som upprätthåller en pseudo-triangulering i $O(n^{2}2^{\sqrt {\log n\log \log n}})$ händelser totalt. Alla händelser är externa och kräver $O(\lg n)$ tid att bearbeta.