Kinetisk datastruktur

En kinetisk datastruktur är en datastruktur som används för att spåra ett attribut för ett geometriskt system som rör sig kontinuerligt. Till exempel bibehåller en kinetisk konvex skrovdatastruktur det konvexa skrovet för en grupp av $n$ rörliga punkter. Utvecklingen av kinetiska datastrukturer motiverades av beräkningsgeometriska problem som involverade fysiska objekt i kontinuerlig rörelse, såsom kollision eller synlighetsdetektering inom robotik, animation eller datorgrafik.

Översikt

Kinetiska datastrukturer används på system där det finns en uppsättning värden som förändras som en funktion av tiden, på ett känt sätt. Så systemet har några värden, och för varje värde $v$ är det känt att $v=f(t)$ . Kinetiska datastrukturer tillåter frågor på ett system vid den aktuella virtuella tiden $\displaystyle t}$ och två ytterligare operationer:

${\textrm {advance}}(t)$ : Flyttar fram systemet till tid $t$ .
${\textrm {change}}(v,f(t))$ : Ändrar banan för värdet $v$ till $f( t)$ , från och med den aktuella tiden.

Ytterligare operationer kan stödjas. Till exempel används ofta kinetiska datastrukturer med en uppsättning punkter. I det här fallet tillåter strukturen vanligtvis att punkter infogas och tas bort.

Kontrast med traditionella datastrukturer

En kinetisk datastruktur tillåter att värdena som lagras i den ändras kontinuerligt med tiden. I princip kan detta approximeras genom att sampla punkternas position med fasta tidsintervall, och radera och återinsätta varje punkt i en "statisk" (traditionell) datastruktur. Ett sådant tillvägagångssätt är dock sårbart för översampling eller undersampling, beroende på vilket tidsintervall som används, och kan också vara slöseri med beräkningsresurser.

Certifikat tillvägagångssätt

Följande allmänna tillvägagångssätt kan användas för att konstruera kinetiska datastrukturer:

Lagra en datastruktur på systemet vid den aktuella tiden $\displaystyle t}$ . Denna datastruktur tillåter förfrågningar på systemet vid den aktuella virtuella tiden.
Förstärk datastrukturen med certifikat. Certifikat är villkor under vilka datastrukturen är korrekt. Certifikaten är alla sanna nu, och datastrukturen kommer bara att upphöra att vara korrekt när ett av certifikaten inte längre är sant.
Beräkna feltiden för varje certifikat, den tid då det kommer att upphöra att vara sant.
Lagra certifikaten i en prioriterad kö, med hjälp av deras feltider
För att gå vidare till tid $t$ , titta på certifikatet med den lägsta feltiden från prioritetskön. Om certifikatet misslyckas före tidpunkten $t$ , poppar du det från kön och fixar datastrukturen så att den är korrekt vid tidpunkten för felet, och uppdaterar certifikaten. Upprepa detta tills certifikatet med den lägsta feltiden i prioritetskön misslyckas efter tiden t {\ $t}$ . Om certifikatet med den lägsta feltiden i prioritetskön misslyckas efter tiden $t$ , är alla certifikat sanna vid tidpunkten $t$ så att datastrukturen kan svara korrekt på frågor vid tidpunkten $t$ .

Typer av händelser

Certifikatfel kallas "händelser". En händelse anses vara intern om egenskapen som underhålls av den kinetiska datastrukturen inte ändras när händelsen inträffar. En händelse anses vara extern om egenskapen som underhålls av datastrukturen ändras när händelsen inträffar.

Prestanda

När du använder certifikatmetoden finns det fyra mått på prestanda. Vi säger att en kvantitet är liten om den är en polylogaritmisk funktion av $n$ , eller är $O(n^{\epsilon })$ för godtyckligt liten $\epsilon$ , där $n$ är antalet objekt:

Lyhördhet

Respons är den tid som i värsta fall krävs för att fixa datastrukturen och utöka certifikaten när ett certifikat misslyckas. En kinetisk datastruktur är lyhörd om den tid som i värsta fall krävs för en uppdatering är liten.

Lokalitet

Det maximala antalet certifikat som ett värde är involverat i. För strukturer som involverar rörliga punkter är detta det maximala antalet certifikat som en punkt är involverad i. En kinetisk datastruktur är lokal om det maximala antalet certifikat som ett värde är involverat i är liten.

Kompakthet

Det maximala antalet certifikat som används för att utöka datastrukturen när som helst. En kinetisk datastruktur är kompakt om antalet certifikat den använder är $O(n\operatorname {polylog} n)$ eller $O(n^ {1+\epsilon })$ för godtyckligt liten $\epsilon$ . (en liten faktor mer än linjärt utrymme)

Effektivitet

Förhållandet mellan antalet händelser i värsta fall som kan inträffa när strukturen flyttas till $t=\infty$ och antalet "nödvändiga ändringar" i datastrukturen i värsta fall. Definitionen av "nödvändiga förändringar" är problemberoende. Till exempel, i fallet med en kinetisk datastruktur som upprätthåller det kinetiska skrovet för en uppsättning rörliga punkter, skulle antalet nödvändiga ändringar vara antalet gånger det kinetiska skrovet ändras när tiden flyttas till t = ∞ { $= \infty }$ . En kinetisk datastruktur sägs vara effektiv om detta förhållande är litet.

Typer av banor

Prestandan hos en viss kinetisk datastruktur kan analyseras för vissa typer av banor. Vanligtvis övervägs följande typer av banor:

Affine :(linjära funktioner) $f(t)=at+b$
Begränsad gradalgebraisk :(Polynomfunktioner av begränsad grad) $f(t)=\sum _{i=0}^{n}a_{i}t ^{i}$ för några fasta $n$ .
Pseudo-algebraisk : Banor så att alla intressebevis växlar mellan sant och falskt $O(1)$ gånger.

Exempel