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

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

Набор плоских точек [ править ]

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

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

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

Ссылки [ править ]

Александрон, Гиора; Каплан, Хаим; Шарир, Миха (2005), «Кинетические и динамические структуры данных для выпуклых оболочек и верхних оболочек», Алгоритмы и структуры данных (WADS 2005) , Конспекты лекций по информатике, том. 3608, Берлин: Springer, стр. 269–281, номер документа : 10.1007/11534273_24 , MR 2200329.
Бродал, Герт Столтинг; Джейкоб, Рико (2000), «Динамическая плоская выпуклая оболочка с оптимальным временем запроса и $O(\log n\cdot \log \log n)$ время обновления», Теория алгоритмов (SWAT 2000, Берген) , Конспекты лекций по информатике, том 1851, Берлин: Springer, стр. 57–70, doi : 10.1007/3-540-44985-X_7 , MR 1792585
Чан, Тимоти М. (2001), «Динамические операции с плоской выпуклой оболочкой в почти логарифмическом амортизированном времени», Журнал ACM , 48 (1): 1–12, doi : 10.1145/363647.363652 , MR 1867273
Чан, Тимоти М. (2010), «Динамическая структура данных для трехмерных выпуклых оболочек и двумерных запросов к ближайшему соседу», Журнал ACM , 57 (3): A16:1–A16:15, doi : 10.1145 /1706591.1706596 , МР 2665885
Чан, Тимоти М. (2012), «Три проблемы о динамических выпуклых оболочках», Международный журнал вычислительной геометрии и приложений , 22 (4): 341–364, doi : 10.1142/S0218195912600096 , MR 2994585
Демейн, Эрик Д .; Путрашку, Михай (2007), «Жесткие границы для запросов динамической выпуклой оболочки (снова)», Proc. Симп. Вычислительная геометрия (SoCG 2007) , Нью-Йорк: ACM, стр. 354–363, doi : 10.1145/1247069.1247131 , MR 2469185
Хершбергер, Джон ; Сури, Субхаш (1992), «Применение полудинамического алгоритма выпуклой оболочки», BIT , 32 (2): 249–267, doi : 10.1007/BF01994880 , MR 1172189
О, Ынджин; Ан, Хи-Кап (2017), «Динамические геодезические выпуклые оболочки в динамических простых многоугольниках», 33-й Международный симпозиум по вычислительной геометрии (SoCG 2017) , LIPIcs, vol. 77, Schloss Dagstuhl, стр. 51:1–51:15, doi : 10.4230/LIPIcs.SoCG.2017.51 , MR 3685723
Овермарс, Миннесота ; ван Леувен, Дж. (1981), «Поддержание конфигураций в плоскости», Журнал компьютерных и системных наук , 23 (2): 166–204, doi : 10.1016/0022-0000(81)90012-X .