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

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

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

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

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

• Александрон, Гиора; Каплан, Хаим; Шарир, Миха (2005), «Кинетические и динамические структуры данных для выпуклых оболочек и верхних оболочек», Алгоритмы и структуры данных (WADS 2005) , Lecture Notes in Computer Science, т. 3608, Берлин: Springer, стр.  269–281 , doi :10.1007/11534273_24, ISBN 978-3-540-28101-6, МР  2200329
• Brodal, Gerth Stølting; Jacob, Riko (2000), "Динамическая плоская выпуклая оболочка с оптимальным временем запроса и обновления", Algorithm Theory (SWAT 2000, Берген) , Lecture Notes in Computer Science, т. 1851, Берлин: Springer, стр.  57–70 , doi :10.1007/3-540-44985-X_7, ISBN${\displaystyle O(\log n\cdot \log \log n)}$ 978-3-540-67690-4, г-н  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, MR  2665885
• Чан, Тимоти М. (2012), «Три проблемы о динамических выпуклых оболочках», Международный журнал вычислительной геометрии и приложений , 22 (4): 341– 364, doi :10.1142/S0218195912600096, MR  2994585
• Demaine, Erik D. ; Pǎtraşcu, Mihai (2007), "Жесткие границы для динамических запросов выпуклой оболочки (снова)", Proc. Symp. Computational Geometry (SoCG 2007) , Нью-Йорк: ACM, стр.  354–363 , doi :10.1145/1247069.1247131, ISBN 978-1-59593-705-6, г-н  2469185
• Хершбергер, Джон ; Сури, Субхаш (1992), «Применение алгоритма полудинамической выпуклой оболочки», BIT , 32 (2): 249– 267, doi :10.1007/BF01994880, MR  1172189
• О, Ынджин; Ан, Хи-Кап (2017), «Динамические геодезические выпуклые оболочки в динамических простых многоугольниках», 33-й Международный симпозиум по вычислительной геометрии (SoCG 2017) , LIPIcs, т. 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.