Кинетическая минимальная коробка - Kinetic minimum box

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

2D корпус

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

в двойной посмотреть, где точка (а, б) сопоставляется с линией у=аИкс+б, вычисляются четыре конверта (левый, правый, верхний, нижний). Диапазон значений x линейного сегмента в одной из этих огибающих соответствует диапазону поддерживающих наклонов соответствующей вершины выпуклой оболочки на прямом виде. Таким образом, интервал, в котором значения x четырех списков огибающих перекрываются (что может быть получено путем объединения списков), соответствует, в основном виде, диапазону наклона, где все линии, параллельные и перпендикулярные наклонам, поддерживают одни и те же четыре выпуклых вершины корпуса. Минимальный прямоугольник (с точки зрения площади или периметра) можно легко вычислить для каждого диапазона уклона и четырех поддерживаемых таким образом вершин, а затем можно найти глобальный минимальный прямоугольник, минимизируя эти интервалы. Этот алгоритм можно кинетизировать, сохраняя выпуклую оболочку в кинетическая выпуклая оболочка структура данных, слияние четырех списков конвертов в кинетический отсортированный список и коробки в очередь с кинетическим приоритетом.

Анализ

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

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

1. Агарвал, Панкадж; Guibas, Leonidas J .; Хершбергер, Джон; Эрик Вич (1997). Сохранение протяженности набора движущихся точек (PDF). SCG. ACM. Получено 19 мая, 2012.