Кинетическая триангуляция

кинетическая структура Структура данных кинетической триангуляции — это данных , которая поддерживает триангуляцию набора движущихся точек. Поддержание кинетической триангуляции важно для приложений, включающих планирование движения , таких как видеоигры, виртуальная реальность, динамическое моделирование и робототехника.

Выбор схемы триангуляции

Эффективность кинетической структуры данных определяется на основе отношения количества внутренних событий к внешним событиям, поэтому хорошие границы времени выполнения иногда можно получить, выбрав использование схемы триангуляции, которая генерирует небольшое количество внешних событий.Для простого аффинного движения точек количество дискретных изменений выпуклой оболочки оценивается выражением $\Omega (n^{2})$, таким образом, количество изменений в любой триангуляции также ограничено снизу $\Omega (n^{2})$. Поиск любой схемы триангуляции, которая имеет почти квадратичную границу числа дискретных изменений, является важной открытой проблемой.

Триангуляция Делоне

Триангуляция Делоне кажется естественным кандидатом, но тщательный анализ наихудшего случая количества дискретных изменений, которые произойдут в триангуляции Делоне (внешние события), считался открытой проблемой до 2015 года; теперь это должно было быть между $\Omega (n^{2})$ и $O(n^{2+\epsilon })$.

Существует кинетическая структура данных, которая эффективно поддерживает триангуляцию Делоне набора движущихся точек. в котором отношение общего числа событий к числу внешних событий равно $O(1)$.

Другие триангуляции

Каплан и др. разработал рандомизированную схему триангуляции, которая испытывает ожидаемое количество $O(n^{2}\beta _{s+2}(n)\log ^{2}n)$ внешние события, в которых $s$ - максимальное количество раз, когда каждая тройка точек может стать коллинеарной, $\beta _{s+2}(q)={\frac {\lambda _{s+2}(q)}{q}}$, и $\lambda _{s+2}(q)$ — максимальная длина последовательности Давенпорта-Шинзеля порядка s + 2 на n символах.

Псевдотриангуляции

Существует кинетическая структура данных (автор Агарвал и др.), которая поддерживает псевдотриангуляцию в $O(n^{2}2^{\sqrt {\log n\log \log n}})$ событий всего. Все события являются внешними и требуют $O(\lg n)$ время обрабатывать.