Kinetyczny najmniejszy otaczający dysk
Kinetyczna najmniejsza otaczająca struktura danych dysku to kinetyczna struktura danych , która utrzymuje najmniejszy otaczający dysk zestawu ruchomych punktów.
2D
W 2 wymiarach najbardziej znana kinetyczna struktura danych najmniejszego otaczającego dysku wykorzystuje triangulację delaunay najdalszego punktu zbioru punktów w celu utrzymania najmniejszego otaczającego dysku. Triangulacja Delaunaya najdalszego punktu jest podwójna diagramu Woronoja najdalszego punktu . Wiadomo, że jeśli triangulacja delaunay najdalszego punktu zbioru punktów zawiera trójkąt ostry, to okrąg opisany na tym trójkącie jest najmniejszym otaczającym dyskiem. W przeciwnym razie najmniejszy otaczający dysk ma średnicę punktu ustawionego jako średnica. W ten sposób, utrzymując średnicę kinetyczną zbioru punktów, triangulacji delaunay najdalszego punktu i niezależnie od tego, czy triangulacja delaunay najdalszego punktu ma trójkąt ostry, można zachować najmniejszy otaczający dysk. Ta struktura danych jest responsywna i zwarta, ale nie jest lokalna ani wydajna:
- Responsywność : Ta struktura danych wymaga a zatem
- Lokalizacja : punkt może być zaangażowany w certyfikaty . W związku z tym ta struktura danych nie jest lokalna.
- Zwartość : ta struktura danych wymaga łącznie O(n) certyfikatów, a zatem jest zwarta.
- Wydajność : Ta struktura danych zawiera dla dolna wydajność tej struktury danych, stosunek wszystkich zdarzeń do zdarzeń zewnętrznych, wynosi .
Istnienie kinetycznej struktury danych ,
Przybliżony 2D
dysk zbioru n ruchomych punktów można kinetycznej danych przetwarza i wymaga całkowitego czasu
Wyższe wymiary
W wymiarach większych niż 2 efektywne utrzymanie najmniejszej otaczającej sfery zbioru ruchomych punktów jest problemem otwartym.