Pudełko minimum kinetycznego
Kinetyczna ramka minimum to kinetyczna struktura danych służąca do utrzymania minimalnej ramki ograniczającej zbiór punktów, których pozycje zmieniają się w sposób ciągły w czasie. W przypadku punktów poruszających się w płaszczyźnie kinetyczna wypukła struktura danych kadłuba może być wykorzystana jako podstawa do responsywnej, zwartej i wydajnej kinetycznej struktury danych z minimalnym pudełkiem.
obudowa 2D
Pudełko minimum kinetycznego 2D opiera się na kinetycznym wypukłym kadłubie 2D w sposób podobny do struktury danych szerokości kinetycznej , która utrzymuje parę równoległych linii o minimalnej odległości, między którymi znajduje się cały punkt. W tym przypadku, ponieważ pudełko składa się z dwóch par równoległych linii (które są do siebie prostopadłe), można przeprowadzić analogię do dwóch prostopadłych problemów z szerokością kinetyczną, a struktura danych musi utrzymywać zbiory czterech punktów – dwóch antypodów pary, które mają prostopadłe linie nośne.
W widoku podwójnym , w którym punkt ( a , b ) odwzorowuje linię y = a x + b , obliczane są cztery obwiednie (lewa, prawa, górna, dolna). Zakres wartości x segmentu linii w jednej z tych obwiedni odpowiada zakresowi nachyleń podtrzymujących odpowiedniego wypukłego wierzchołka kadłuba w widoku pierwotnym. Zatem przedział, w którym wartości x czterech list obwiedni nakładają się na siebie (co można uzyskać przez scalenie list), odpowiada w pierwotnym widoku zakresowi nachyleń, w którym wszystkie linie równoległe i prostopadłe do zboczy wspierają te same cztery wypukłe wierzchołki kadłuba. Pudełko minimalne (pod względem powierzchni lub obwodu) można łatwo obliczyć dla każdego zakresu nachylenia i czterech obsługiwanych w ten sposób wierzchołków, a następnie można znaleźć globalne pudełko minimalne, minimalizując te przedziały. Algorytm ten można kinetyzować, utrzymując wypukłą otoczkę w a kinetyczna wypukła struktura danych kadłuba, połączenie czterech list obwiedni w kinetycznie posortowanej liście i pól w kinetycznej kolejce priorytetowej .
Analiza
Responsywność i zwartość tej struktury danych wynikają z kinetycznej wypukłej obudowy, kinetycznej listy posortowanej i kinetycznej kolejki priorytetowej . Jest to również efektywne , ponieważ liczba kombinatorycznie różnych pudełek minimalnych dla n punktów wynosi Istnienie lokalnej struktury danych dla tego problemu jest problemem otwartym.
