Кинетический наименьший охватывающий диск - Kinetic smallest enclosing disk

А кинетический наименьший охватывающий диск структура данных - это кинетическая структура данных который поддерживает наименьший включающий диск набора движущихся точек.

2D

В двух измерениях наиболее известная кинетическая структура данных наименьшего охватывающего диска использует триангуляцию с задержкой по самой дальней точке набора точек для поддержания наименьшего охватывающего диска.^[1] Самая дальняя точка Триангуляция Делоне это двойной из диаграмма Вороного с дальней точкой. Известно, что если триангуляция Делоне самой дальней точки набора точек содержит острый треугольник, то описанный круг этого треугольника - наименьший охватывающий диск. В противном случае наименьший охватывающий диск имеет диаметр точки, установленный как его диаметр. Таким образом, поддерживая кинетический диаметр набора точек, триангуляции Делоне с самой дальней точкой и наличия острого треугольника в самой дальней точке триангуляции Делоне, наименьший охватывающий диск может быть сохранен. Эта структура данных является отзывчивой и компактной, но не локальной или эффективной:^[1]

• Ответная реакция: Эта структура данных требует ${\displaystyle O(\log ^{2}n)}$ время обрабатывать каждый сбой сертификата и, следовательно, реагировать.
• Местонахождение: Точка может быть задействована в ${\displaystyle \Theta (n)}$ сертификаты. Следовательно, эта структура данных не является локальной.
• Компактность: Эта структура данных требует всего O (n) сертификатов и поэтому является компактной.
• Эффективность: Эта структура данных имеет ${\displaystyle O(n^{3+\epsilon })}$ всего мероприятий. (для всех ${\displaystyle \epsilon >0}$ Самая известная нижняя граница количества изменений самого маленького включающего диска - ${\displaystyle \Omega (n^{2})}$. Таким образом, эффективность этой структуры данных, отношение общего количества событий к внешним событиям, составляет ${\displaystyle O(n^{1+\epsilon })}$.

Существование кинетической структуры данных, которая имеет ${\displaystyle o(n^{3+\epsilon })}$ события - открытая проблема.^[1]

Примерное 2D

Наименьший охватывающий диск набора из n движущихся точек может быть ε-аппроксимация кинетической структурой данных, которая обрабатывает ${\displaystyle O(1/\epsilon ^{5/2})}$ события и требует ${\displaystyle O((n/{\sqrt {\epsilon }})\log n)}$ общее время.^[2]

Высшие измерения

В размерах больше 2 эффективное поддержание наименьшей охватывающей сферы из набора движущихся точек является открытой проблемой.^[1]

Рекомендации

1. Эрик Д. Демейн, Сара Эйзенстат, Леонидас Дж. Гибас, Андре Шульц, Кинетический минимальный остовный круг, 2010. [1]
2. Панкадж К. Агарвал и Сариэль Хал-Пелед. Сохранение приблизительных размеров движущихся точек. В SODA '01: Материалы двенадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, страницы 148–157, Филадельфия, Пенсильвания, США, 2001. Общество промышленной и прикладной математики.