Кинетическая структура данных - Kinetic data structure

А кинетическая структура данных это структура данных используется для отслеживания атрибута непрерывно движущейся геометрической системы.^[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. Чтобы продвинуться во времени ${\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. Гибас, Леонидас Дж. (2001), «Кинетические структуры данных» (PDF), в Mehta, Dinesh P .; Сахни, Сартадж (ред.), Справочник по структурам данных и приложениям, Chapman and Hall / CRC, стр. 23-1–23-18, ISBN  978-1-58488-435-4
3. Абам, Мохаммед Али (2007). Новые структуры данных и алгоритмы для мобильных данных (Тезис). Эйндховенский технологический университет.
4. Рахмати, Захед (2014). Простые и быстрые кинетические структуры данных (Тезис). Университет Виктории. HDL:1828/5627.
5. Гибас, Леонидас Дж. (1998), «Кинетические структуры данных: современный отчет» (PDF), в Agarwal, Pankaj K .; Кавраки, Лидия Э .; Мейсон, Мэтью Т. (ред.), Робототехника: алгоритмическая перспектива (материалы 3-го семинара по алгоритмическим основам робототехники), А. К. Питерс / CRC Press, стр. 191–209, ISBN  978-1-56881-081-2

внешняя ссылка