Структура кинетических данных

Структуры данных, используемые для отслеживания непрерывно движущихся геометрических тел

Кинетическая структура данных — это структура данных, используемая для отслеживания атрибута геометрической системы, которая непрерывно движется. ^{[1] [2] [3] [4]} Например, кинетическая структура данных выпуклой оболочки поддерживает выпуклую оболочку группы движущихся точек. Разработка кинетических структур данных была мотивирована проблемами вычислительной геометрии , включающими физические объекты в непрерывном движении, такими как обнаружение столкновений или видимости в робототехнике, анимации или компьютерной графике. ${\displaystyle n}$

Обзор

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

• ${\displaystyle {\textrm {advance}}(t)}$: Перемещает систему на время . ${\displaystyle t}$
• ${\displaystyle {\textrm {change}}(v,f(t))}$: Изменяет траекторию значения на , по состоянию на текущий момент времени. ${\displaystyle v}$ ${\displaystyle f(t)}$

Могут поддерживаться дополнительные операции. Например, кинетические структуры данных часто используются с набором точек. В этом случае структура обычно позволяет вставлять и удалять точки.

Контраст с традиционными структурами данных

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

Сертификаты подход

Для построения кинетических структур данных можно использовать следующий общий подход: ^[5]

1. Сохраните структуру данных в системе в текущий момент времени . Эта структура данных позволяет выполнять запросы в системе в текущий виртуальный момент времени. ${\displaystyle t}$
2. Дополните структуру данных сертификатами. Сертификаты — это условия, при которых структура данных точна. Все сертификаты сейчас верны, и структура данных перестанет быть точной только тогда, когда один из сертификатов перестанет быть верным.
3. Вычислите время отказа каждого сертификата, время, когда он перестанет быть истинным.
4. Сохраните сертификаты в приоритетной очереди, упорядоченной по времени их отказа.
5. Чтобы перейти к time , посмотрите на сертификат с наименьшим временем сбоя из очереди приоритетов. Если сертификат дает сбой до time , извлеките его из очереди и исправьте структуру данных, чтобы она была точной на момент сбоя, и обновите сертификаты. Повторяйте это до тех пор, пока сертификат с наименьшим временем сбоя в очереди приоритетов не даст сбой после time . Если сертификат с наименьшим временем сбоя в очереди приоритетов даст сбой после time , то все сертификаты истинны в time , поэтому структура данных может правильно отвечать на запросы в time . ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$

Типы мероприятий

Сбои сертификатов называются «событиями». Событие считается внутренним, если свойство, поддерживаемое кинетической структурой данных, не изменяется при возникновении события. Событие считается внешним, если свойство, поддерживаемое структурой данных, изменяется при возникновении события.

Производительность

При использовании подхода с сертификатами есть четыре показателя производительности. Мы говорим, что величина мала, если она является полилогарифмической функцией , или является для произвольно малого , где — количество объектов: ${\displaystyle n}$ ${\displaystyle O(n^{\epsilon })}$ ${\displaystyle \epsilon }$ ${\displaystyle n}$

Отзывчивость

Отзывчивость — это наихудшее количество времени, необходимое для исправления структуры данных и дополнения сертификатов при сбое сертификата. Кинетическая структура данных отзывчива, если наихудшее количество времени, необходимое для обновления, невелико.

Местность

Максимальное количество сертификатов, в которых участвует любое одно значение. Для структур, включающих движущиеся точки, это максимальное количество сертификатов, в которых участвует любая одна точка. Кинетическая структура данных является локальной, если максимальное количество сертификатов, в которых участвует любое одно значение, невелико.

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

Максимальное количество сертификатов, используемых для расширения структуры данных в любой момент времени. Кинетическая структура данных является компактной, если количество сертификатов, которые она использует, равно или для произвольно малого . (небольшой фактор больше линейного пространства) ${\displaystyle O(n\operatorname {polylog} n)}$ ${\displaystyle O(n^{1+\epsilon })}$ ${\displaystyle \epsilon }$

Эффективность

Отношение наихудшего числа событий, которые могут произойти при продвижении структуры к наихудшему числу «необходимых изменений» в структуре данных. Определение «необходимых изменений» зависит от проблемы. Например, в случае кинетической структуры данных, поддерживающей кинетическую оболочку набора движущихся точек, число необходимых изменений будет равно числу раз, которое кинетическая оболочка изменится по мере продвижения времени к . Кинетическая структура данных считается эффективной, если это отношение мало. ${\displaystyle t=\infty }$ ${\displaystyle t=\infty }$

Типы траекторий

Эффективность определенной кинетической структуры данных может быть проанализирована для определенных типов траекторий. Обычно рассматриваются следующие типы траекторий:

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

Примеры

• Кинетический турнир
• Кинетический отсортированный список
• Кинетическая куча
• Кинетическая выпуклая оболочка
• Кинетическая ближайшая пара
• Кинетическое минимальное остовное дерево
• Кинетическое евклидово минимальное остовное дерево

Ссылки

1. Баш, Жюльен (1999). Кинетические структуры данных (диссертация). Стэнфордский университет.
2. Guibas, Leonidas J. (2001), «Кинетические структуры данных» (PDF) , в Mehta, Dinesh P.; Sahni, Sartaj (ред.), Handbook of Data Structures and Applications , Chapman and Hall/CRC, стр. 23-1–23-18, ISBN 978-1-58488-435-4
3. Абам, Мохаммад Али (2007). Новые структуры данных и алгоритмы для мобильных данных (диссертация). Эйндховенский технологический университет.
4. Рахмати, Захед (2014). Простые, более быстрые кинетические структуры данных (диссертация). Университет Виктории. hdl :1828/5627.
5. Guibas, Leonidas J. (1998), «Кинетические структуры данных: отчет о состоянии дел» (PDF) , в Agarwal, Pankaj K.; Kavraki, Lydia E.; Mason, Matthew T. (ред.), Robotics: The Algorithmic Perspective (Труды 3-го семинара по алгоритмическим основам робототехники) , AK Peters/CRC Press, стр. 191–209, ISBN 978-1-56881-081-2