Kinetyczna struktura danych

Kinetyczna struktura danych to struktura danych używana do śledzenia atrybutu układu geometrycznego, który porusza się w sposób ciągły. $Na$ przykład kadłuba kinetycznego wypukłego utrzymuje wypukły kadłub grupy ruchomych punktów. Rozwój struktur danych kinetycznych był motywowany geometrii obliczeniowej obejmującymi obiekty fizyczne w ciągłym ruchu, takimi jak wykrywanie kolizji lub widoczności w robotyce, animacji lub grafice komputerowej.

Przegląd

Struktury danych kinetycznych są używane w systemach, w których istnieje zestaw wartości zmieniających się w funkcji czasu w znany sposób. Tak więc system ma pewne wartości i dla każdej wartości $v = f (t)}$ , że $displaystyle$ . Struktury danych kinetycznych umożliwiają zapytania w systemie w bieżącym czasie wirtualnym i dwie dodatkowe operacje: ${\ displaystyle t}$

${\ Displaystyle {\ textrm {zaliczka}} (t)}$ : przesuwa system do czasu ${\ displaystyle t}$ .
${\ Displaystyle {\ textrm {zmiana}} (v, f (t))}$ : Zmienia trajektorię wartości ${\ Displaystyle v}$ na ${\ Displaystyle f ( t)}$ , od chwili obecnej.

Mogą być obsługiwane dodatkowe operacje. Na przykład kinetyczne struktury danych są często używane z zestawem punktów. W takim przypadku struktura zazwyczaj umożliwia wstawianie i usuwanie punktów.

Porównaj z tradycyjnymi strukturami danych

Kinetyczna struktura danych pozwala na ciągłe zmiany przechowywanych w niej wartości w czasie. W zasadzie można to przybliżyć poprzez próbkowanie położenia punktów w ustalonych odstępach czasu oraz usuwanie i ponowne wstawianie każdego punktu do „statycznej” (tradycyjnej) struktury danych. Jednak takie podejście jest podatne na nadpróbkowanie lub niedopróbkowanie, w zależności od zastosowanego przedziału czasu, a także może być marnotrawstwem zasobów obliczeniowych.

Podejście do certyfikatów

Do konstruowania kinetycznych struktur danych można zastosować następujące ogólne podejście:

Przechowuj strukturę danych w systemie w bieżącym czasie ${\ displaystyle t}$ . Ta struktura danych umożliwia zapytania w systemie w bieżącym czasie wirtualnym.
Rozszerz strukturę danych o certyfikaty. Certyfikaty to warunki, w których struktura danych jest dokładna. Wszystkie certyfikaty są teraz prawdziwe, a struktura danych przestanie być dokładna dopiero wtedy, gdy jeden z certyfikatów przestanie być prawdziwy.
Oblicz czas awarii każdego certyfikatu, czas, kiedy przestanie być prawdziwy.
Przechowuj certyfikaty w kolejce priorytetowej, której kluczem jest czas ich awarii
Aby przejść do czasu $.$ spójrz na certyfikat z najniższym czasem awarii z kolejki priorytetów Jeśli certyfikat ulegnie awarii przed $upływem$ , wyjmij go z kolejki i napraw strukturę danych, aby była dokładna w momencie awarii, i zaktualizuj certyfikaty. Powtarzaj to, aż certyfikat o najniższym czasie awarii w kolejce priorytetów ulegnie awarii po czasie ${\ displaystyle t}$ . Jeśli certyfikat o najniższym czasie awarii w kolejce priorytetów ulegnie awarii po czasie ${\ displaystyle t}$ , to wszystkie certyfikaty są prawdziwe w czasie, $\ displaystyle t} t {$ struktura danych może poprawnie odpowiadać na zapytania w czasie $\ displaystyle t}$ .

Rodzaje wydarzeń

Awarie certyfikatów są określane jako „zdarzenia”. Zdarzenie jest uważane za wewnętrzne, jeśli właściwość utrzymywana przez strukturę danych kinetycznych nie zmienia się po wystąpieniu zdarzenia. Zdarzenie jest uważane za zewnętrzne, jeśli właściwość utrzymywana przez strukturę danych zmienia się po wystąpieniu zdarzenia.

Wydajność

Podczas korzystania z podejścia opartego na certyfikatach istnieją cztery miary wydajności. Mówimy, że wielkość $dowolnie$ $funkcją$ $polilogarytmiczną$ lub jest dla małej , gdzie jest liczbą obiektów: ${\ displaystyle n}$

Reakcja na coś

Responsywność to w najgorszym przypadku ilość czasu wymagana do naprawienia struktury danych i rozszerzenia certyfikatów w przypadku niepowodzenia certyfikatu. Struktura danych kinetycznych jest responsywna, jeśli w najgorszym przypadku czas wymagany do aktualizacji jest niewielki.

Miejscowość

Maksymalna liczba certyfikatów, których dotyczy dowolna wartość. W przypadku struktur obejmujących ruchome punkty jest to maksymalna liczba certyfikatów, w które zaangażowany jest dowolny punkt. Struktura danych kinetycznych jest lokalna, jeśli maksymalna liczba certyfikatów dotyczy dowolnej wartości jest mały.

Ścisłość

Maksymalna liczba certyfikatów używanych do rozszerzenia struktury danych w dowolnym momencie. Kinetyczna struktura danych jest zwarta, jeśli liczba używanych przez nią certyfikatów wynosi ${\ Displaystyle O (n \ operatorname {polylog} n)}$ lub ${\ Displaystyle O (n ^ {1+ \ epsilon}}}$ dla dowolnie małych ${\ displaystyle \ epsilon}$ . (mały współczynnik większy niż przestrzeń liniowa)

Efektywność

Stosunek liczby zdarzeń w najgorszym przypadku, które mogą wystąpić, gdy struktura zostanie rozszerzona $najgorszym$ liczby „niezbędnych zmian” w strukturze danych w Definicja „niezbędnych zmian” zależy od problemu. Na przykład w przypadku kinetycznej struktury danych utrzymującej kinetyczny kadłub zestawu ruchomych punktów, liczba niezbędnych zmian byłaby liczbą zmian kadłuba kinetycznego w miarę upływu czasu do t = ∞ { $= \infty}$ . Mówi się, że kinetyczna struktura danych jest wydajna, jeśli ten stosunek jest mały.

Rodzaje trajektorii

Działanie określonej kinetycznej struktury danych można analizować dla określonych typów trajektorii. Zazwyczaj brane są pod uwagę następujące typy trajektorii:

afiniczny :(funkcje liniowe) ${\ Displaystyle f (t) = at + b}$
algebraiczny stopnia ograniczonego :( funkcje wielomianowe stopnia ograniczonego) ${\ Displaystyle f (t) = \ suma _ {i = 0} ^ {n} a_ {i} t ^ {i}}$ dla niektórych stałych ${\ displaystyle n}$ .
Pseudo-algebraiczne : Trajektorie takie, że każdy certyfikat będący przedmiotem zainteresowania zmienia się między prawdą a fałszem razy ${\ Displaystyle O (1)} .$

Przykłady