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.