Сублинейный, но простой алгоритм динамической выпуклой оболочки?

Question

Мне нужно решить проблему с алгоритмом динамического выпуклого корпуса, т. Е. Поддерживать выпуклый корпус двумерных точек, где я могу добавлять и удалять точки.

Наивный подход явно O(N);всякий раз, когда одна из N точек добавляется / удаляется, мы заново вычисляем выпуклую оболочку с нуля.Однако я не могу позволить себе линейное время, поэтому я ищу сублинейный алгоритм.До сих пор я нашел пачку статей, в которых описан какой-то сложный алгоритм с безумными временными рамками, на реализацию которого потребовались бы годы.Даже самый старый эффективный алгоритм из-за Overmars и Leeuween, который является O(log^2 N), кажется слишком сложным.(Как обычно, большинство алгоритмов, описанных в таких статьях, имеют тонны зависимостей в терминах структур / алгоритмов из других упомянутых статей)чем линейный в худшем случае (например, O(sqrt N)).Наконец, я не против, если время амортизируется.Любые идеи?

(Под простым я в первую очередь имею в виду то, что не требует более нескольких сотен строк кода.)

Answer 1

Я думаю, что вы ищете, не существует.Алгоритм Овермара и Ван Лееувена не так уж сложен, и в некотором смысле кажется необходимым.Во-первых, измените проблему на поддержание верхнего корпуса и нижнего корпуса отдельно.Во-вторых, создайте каждый из них методом «разделяй и властвуй», но сохраняйте промежуточные древовидные структуры, чтобы вы знали оболочки 1/2-множеств, 1/4-множества и т. Д. Теперь, когда вы удаляете точку, выпересчитать только своих предков в дереве.Когда вы добавляете точку, вы узнаете, к какому листу она присоединяется, и снова пересчитываете вверх до корня.

Я думаю, что если вы проигнорируете детали в их статье и просто последуете этому высокоуровневому эскизу, иВыполните все шаги самым бессмысленным образом, это не будет сложным и будет сублинейным.

М.Х. Овермарс и Дж. Ван Леувен.Поддержание конфигураций в самолете. J.Вычи.Сист.Sci. , 23: 166-204, 1981.

Answer 2

Что касается профессора О'Рурка, который знает гораздо больше, чем я когда-либо знаю о вычислительной геометрии, я не вижу, как «бессмысленная» реализация OvL (то есть, без ребалансировки) могла бы быть сублинейной в худшем случае .

К счастью, мы добились некоторых успехов в структурах данных с 1981 года. В частности, поскольку достаточно амортизированной гарантии, деревья сплайсов (1985) подходят для хранения обоих выпуклых оболочеки дерево слияния. Austern et al.(2003) предложил хороший способ отделить ведение дополнительных полей, которые потребуются от сложных операций балансировки, так что вы можете написать сложные части один раз.

Основная трудность в реализации Splay Treeэто операция сплайна, и даже это намного проще, чем, скажем, вставить в красно-черное дерево.Как только Splay работает, деревья Splay легко разделяются и объединяются.Чтобы разделить, разверните узел, после которого вы хотите разделить, и обрежьте его правого потомка.Чтобы присоединиться, разверните самый правый узел первого дерева и сделайте второе дерево правым потомком этого узла.

Answer 3

Я предполагаю, что всего имеется N точек данных, а сложный корпус определяется M точками.

Поддерживать выпуклый корпус должно быть намного проще (и дешевле), чем строить его в первую очередь.

Удаление существующей точки данных

1/ If the data point in not one of the M points defining the convex hull then it won’t affect the hull so just remove it.

2/ If it is part of the convex hull then you need to adjust the hull – more on that below in point 4

Добавление новой точки данных.

3/ If a data point is inside the complex hull then it will not affect the hull. 

Вотпростой способ проверить это на макушке.Создайте триангуляцию интерьера корпуса.Сложный корпус, определенный с использованием точек M, можно триангулировать в треугольники M-2.Затем проверьте, лежит ли точка в одном из треугольников.

4/ if a data point is outside the hull then it will become part of the hull. However, it is only affecting a local area of the hull and it is straightforward to find the new hull in a few steps. If you have already build the hull then it should be clear to you how to adjust a local part of it.

Я не понимаю, каким образом это обслуживание может быть O (N)