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

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

2D

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

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

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

Примерное 2D

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

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

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

Ссылки

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

[DEGS10-1] Jump up to: ^а ^б ^с ^д Эрик Д. Демейн, Сара Эйзенштат, Леонидас Дж. Гибас , Андре Шульц, Кинетический минимальный охват, 2010. [1]

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

[1]

[2]