Кінетична структура даних

Кінетична структура даних — це структура даних, яка використовується для того, щоб відстежити властивість геометричної системи, що безперервно рухається. Наприклад, кінетична опукла оболонка зберігає опуклу оболонку з $n$ рухомих точок. Розвиток теорії кінетичної структури даних був мотивований задачами обчислювальної геометрії, які розглядають фізичні об'єкти, що безперервно рухаються, наприклад, проблеми зіткнення або видимості у робототехніці, анімації, або у комп'ютерній графіці.

Огляд

Кінетичні структури даних використовуються в системах, де є множина значень, які змінюються з часом відомим способом. Тобто у системи є деякі значення, і для кожного значення $v$ відомо, що $v=f(t)$. Кінетичні структури даних дозволяють виконувати запити до системи у поточний час системи $t$, і припускають дві додаткові операції:

• ${\textrm {advance}}(t)$: Змінювати час системи на $t$.
• ${\textrm {change}}(v,f(t))$: Задати траєкторію параметру $v$ через час $f(t)$.

Також можуть підтримуватись додаткові операції. Наприклад, кінетичні структури даних часто використовуються разом з множиною точок. Природно, що такому випадку, структура дозволяє додавання та видалення точок.

Порівняння з традиційними структурами даних

Кінетична структура даних дозволяє значенням, що збережені в ній, безперервно змінюватись із часом. В принципі, це може бути наближено шляхом підбору положення точок на фіксованих інтервалах часу, і подальшого видалення і вставлення кожної точки в «статичну» (традиційну) структуру даних. Проте, такий підхід уразливий для передискретизації або субсемпліювання в залежності від того, який проміжок часу використовується. Цей підхід також може марнувати обчислювальні ресурси.

Метод ключів

Наступний загальний метод може використовуватись для побудови кінетичних структур даних:

1. Структура даних системи зберігається у поточний момент $t$. Це дозволяє звертатися до системи у фактичний поточний час.
2. Додамо до структури даних ключі. Ключі — це стани системи, коли структура даних точна. На початку усі ключі приймають значення «істина». Структура даних більше не буде точною лише тоді, коли хоча б один з ключів прийме значення «хиба».
3. Підрахуємо час відмови — час, за який ключ змінив значення, тобто час, коли ключ втратить значення «істина».
4. Збережемо ключі у список, впорядкувавши їх по часу відмови, підрахованому вище.
5. Щоб перейти до часу $t$, треба взяти ключ із списку з найнижчим часом відмови. Якщо ключ змінює значення перед часом $t$, треба витягти його зі списку, та зафіксувати структуру даних так, щоб вона була точною у час відмови даного ключа, і потім оновити ключі. Операцію слід повторювати до тих пір, поки ключ із найнижчим часом відмови у списку ключів змінює значення після часу $t$. Якщо ключ із найнижчим часом відмови у списку ключів змінює значення після часу $t$, то усі ключі мають значення «істина» у час $t$, і, таким чином структура даних може правильно відповідати на запити у час $t$.

Типи подій

Зміна значень ключів належить до типу «подій». Подія вважається внутрішньою, якщо властивість, що зумовлена кінетичною структурою даних не змінюється, коли трапляється подія. Подія вважається зовнішньою, якщо властивість, що зумовлена кінетичною структурою даних змінюється, коли трапляється подія.

Продуктивність

При використанні методу ключів є чотири складових вимірювання продуктивності. Скажемо, що покажчик продуктивності найменший, якщо він $O({\textrm {polylog}}(n))$ або $O(n^{\epsilon })$ для довільного малого $\epsilon$, де $n$ — число об'єктів:

Чутливість

Чутливість — це найбільша кількість часу, яка потрібна, щоб оновити структуру даних, коли ключ змінює своє значення. Кінетична структура даних є більш чутливою, чим менша кількість часу, яка потрібна на оновлення даних.

Локальність

Локальність — це максимальна кількість ключів для якогось зі значень. Для структур, що включають рухомі точки, це максимальна кількість ключів для будь-якої точки. Кінетична структура даних є локальною, якщо максимальна кількість ключів для кожного значення мала.

Компактність

Компактність — це максимальна кількість ключів, які були додані до структури у будь-який час. Кінетична структура даних є компактною, якщо кількість ключів, котрі використовує структура є $O(n{\textrm {polylog}}(n))$ або $O(n^{1+\epsilon })$ для довільного малого $\epsilon$.

Точність

Точність — це відношення найгіршого випадку кількості подій, що можуть трапитись, коли структура прив'язана до часу $t=\infty$ до найгіршого випадку кількості «необхідних змін» у структурі даних. Визначення «необхідних змін» залежить від задачі. Кінетична структура даних є точною, якщо це відношення мале.

Типи траєкторій

Продуктивність кінетичної структури даних може бути проаналізована для деяких типів траєкторій. Розрізняють такі типи траєкторій:

• Афінні:(Лінійні функції) $f(t)=at+b$
• Обмежено-степеневі алгебраїчні:(Поліноміальні функції обмеженого ступеня) $f(t)=\sum _{i=0}^{n}a_{i}t^{i}$ для деякого фіксованого $n$.
• Псевдо-алгебраїчні: Траєкторії, де значення будь-якого ключа змінюється $O(1)$ разів.