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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Огляд[ред.ред. код]

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

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

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

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

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

Метод ключів[ред.ред. код]

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

  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_it^i для деякого фіксованого n.
  • Псевдо-алгебраїчні: Траєкторії, де значення будь-якого ключа змінюється O(1) разів.

Посилання[ред.ред. код]

  1. Guibas, Leonidas J. (2001), «Kinetic Data Structures», у Mehta, Dinesh P.; Sahni, Sartaj, Handbook of Data Structures and Applications, Chapman and Hall/CRC, сторінки 23-1–23-18, ISBN 978-1584884354, http://graphics.stanford.edu/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf 
  2. Guibas, Leonidas J. (1998), «Kinetic Data Structures: A State of the Art Report», у Agarwal, Pankaj K.; Kavraki, Lydia E.; Mason, Matthew T., Robotics: The Algorithmic Perspective (Proceedings of the 3rd Workshop on the Algorithmic Foundations of Robotics), A K Peters/CRC Press, сторінки 191–209, ISBN 978-1568810812, http://graphics.stanford.edu/courses/cs428-03-spring/Papers/readings/CollaborativeProcessing/g-kds.pdf