Кинетическая ширина - Kinetic width

А кинетическая ширина структура данных - это кинетическая структура данных который поддерживает ширина набора движущихся точек. В 2D ширина набора точек - это минимальное расстояние между двумя параллельными линиями, которые содержат точку, установленную на полосе между ними. Для двумерного случая кинетическая структура данных для кинетическая выпуклая оболочка может использоваться для построения кинетической структуры данных для ширины набора точек, который отзывчивый, компактный и эффективный.

2D корпус

Рассмотрим параллельные прямые, которые содержат точку, установленную в полосе между ними, и находятся на минимальном расстоянии друг от друга. Одна из линий должна содержать ребро ${\displaystyle ab}$ выпуклой оболочки, а другая линия должна проходить через точку c выпуклой оболочки так, чтобы (a, c) и (b, c) были антиподальные пары. ab и c называются противоположной парой ребро-вершина. двойной набора точек. Точки дуализуются к линиям, а выпуклая оболочка точек дуализируется к верхней и нижней оболочкам набора линий. Вершины верхней выпуклой оболочки дуализуются на сегменты верхней оболочки. Вершины нижней выпуклой оболочки дуализуются на сегменты нижней оболочки. Диапазон наклонов опорных линий точки на корпусе дуализируется до x-интервала сегмента, к которому дуализируется точка. Если смотреть в этом дуализированном виде, пары антиподов представляют собой пары сегментов, один из верхней оболочки, другой из нижней, с перекрывающимися диапазонами x. Теперь верхний и нижний конверты можно рассматривать как два разных х-упорядоченных списка неперекрывающихся интервалов. Если эти два списка объединены, противоположные пары будут перекрываться в объединенном списке. Если пара ${\displaystyle ab}$ и c является антиподальной парой ребро-вершина, тогда x-интервал для a и b должен пересекать x-интервал для c. Это означает, что общая конечная точка интервалов x для a и b должна лежать в пределах x-интервала для c.

Конечные точки обоих наборов x-интервалов могут поддерживаться в кинетический отсортированный список. Когда точки меняются местами, список пар противоположных кромок обновляется соответствующим образом. Верхний и нижний конверты могут поддерживаться с использованием стандартной структуры данных для кинетическая выпуклая оболочка. Минимальное расстояние между парами кромочных точек можно поддерживать с помощью кинетический турнир. Таким образом, используя кинетическую выпуклую оболочку для поддержания верхней и нижней огибающих, кинетический отсортированный список на этих интервалах, чтобы поддерживать пары противоположных ребер-вершин, и кинетический турнир для поддержания пары минимального расстояния друг от друга, диаметр движущейся точки задается можно поддерживать.

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

Существование локальной кинетической структуры данных для ширины открыто.

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

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

Связанные проблемы

• Кинетический диаметр
• Кинетическая минимальная коробка

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

1. Гибас, Леонидас Дж. (2001), «Кинетические структуры данных» (PDF), в Mehta, Dinesh P .; Сахни, Сартадж (ред.), Справочник по структурам данных и приложениям, Chapman and Hall / CRC, стр. 23-1–23-18, ISBN  978-1584884354

дальнейшее чтение

П. К. Агарвал, Л. Дж. Гибас, Дж. Хершбергер и Э. Верах. Сохранение протяженности подвижного набора точек.