Kinetisk minsta omslutande skiva

En kinetisk minsta omslutande diskdatastruktur är en kinetisk datastruktur som upprätthåller den minsta omslutande disken av en uppsättning rörliga punkter.

2D

I 2 dimensioner använder den mest kända kinetiska minsta omslutande skivans datastruktur den längsta punkten fördröjningstriangulering av punktuppsättningen för att bibehålla den minsta omslutande skivan. Delaunay-trianguleringen med längst bort punkten är dualen av Voronoi-diagrammet med längst bort . Det är känt att om trianguleringen av den längsta punkten av en punktuppsättning innehåller en spetsig triangel, är den omslutna cirkeln av denna triangel den minsta omslutande skivan. Annars har den minsta omslutande skivan spetsens diameter inställd som dess diameter. Sålunda, genom att bibehålla den kinetiska diametern för punktuppsättningen, den längsta punktens delaunay-triangulering, och oavsett om den längsta punkten delaunay-trianguleringen har en spetsig triangel eller inte, kan den minsta omslutande skivan bibehållas. Denna datastruktur är lyhörd och kompakt, men inte lokal eller effektiv:

• Lyhördhet : Denna datastruktur kräver $O(\log ^{2}n)$ tid för att bearbeta varje certifikatfel och är därför lyhörd.
• Lokalitet : En punkt kan vara involverad i $\Theta (n)$ certifikat. Därför är denna datastruktur inte lokal.
• Kompakthet : Denna datastruktur kräver totalt O(n)-certifikat och är därför kompakt.
• Effektivitet : Denna datastruktur har $O(n^{3+\epsilon })$ händelser totalt.(för alla $\epsilon >0$ Den mest kända nedre gränsen på antalet ändringar av den minsta omslutande skivan är ${\displaystyle \Omega (n^{2})}.$ Effektiviteten för denna datastruktur, förhållandet mellan totala händelser och externa händelser, är således $O(n^{1+\epsilon })$ .

Förekomsten av kinetisk datastruktur som har $o(n^{3+\epsilon })$ händelser är ett öppet problem.

Ungefär 2D

Den minsta omslutande skivan av en uppsättning av n rörliga punkter kan ε-approximeras av en kinetisk datastruktur som behandlar $O(1/\epsilon ^{5/2})$ händelser och kräver $O((n/{\sqrt {\epsilon }})\log n)$ total tid.

Högre dimensioner

I dimensioner högre än 2 är det ett öppet problem att effektivt underhålla den minsta omslutande sfären av en uppsättning rörliga punkter.