Динамическая выпуклая оболочка - Dynamic convex hull

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

Набор плоских точек

Легко построить пример, для которого выпуклая оболочка содержит все входные точки, но после вставки единственной точки выпуклая оболочка становится треугольником. И наоборот, удаление одной точки может привести к противоположному резкому изменению размера вывода. Следовательно, если выпуклая оболочка должна быть представлена традиционным способом как многоугольник, нижняя граница в худшем случае вычислительная сложность пересчета выпуклой оболочки есть ${displaystyle Omega (N)}$ , поскольку это время требуется для простого отчета о выходе. Эта нижняя граница достижима, поскольку несколько универсальных алгоритмов выпуклой оболочки работают за линейное время, когда входные точки упорядоченный каким-то образом и методы логарифмического времени для динамического обслуживания упорядоченных данных хорошо известны.

Эту проблему можно решить, сняв ограничение на выходное представление. Существуют структуры данных, которые могут поддерживать представления выпуклой оболочки в течение времени на обновление, которое намного меньше линейного. В течение многих лет лучшим алгоритмом этого типа был алгоритм Овермарса и ван Лиувена (1981), который занимал время O (log² п) за обновление, но с тех пор он был улучшен Тимоти М. Чан и другие.

В ряде приложений поиск выпуклой оболочки является шагом в алгоритме решения общей проблемы. Выбранное представление выпуклой оболочки может повлиять на вычислительную сложность дальнейших операций всего алгоритма. Например, точка в многоугольнике На запрос выпуклого многоугольника, представленного упорядоченным множеством его вершин, можно ответить за логарифмическое время, что было бы невозможно для выпуклых оболочек, о которых сообщает множество его вершин, без какой-либо дополнительной информации. Таким образом, некоторые исследования алгоритмов динамической выпуклой оболочки связаны с вычислительной сложностью различных задачи геометрического поиска с выпуклой оболочкой, хранящейся в определенных типах структур данных. Упомянутый подход Овермарса и ван Левена допускает логарифмическую сложность различных общих запросов.

Динамическая выпуклая оболочка - Dynamic convex hull

Набор плоских точек

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