Мне нужен алгоритм вычисления выпуклой оболочки набора точек из диаграммы Вороного точек за O(n). Диаграмма Вороного содержится в ограничивающей рамке и хранится в виде двусвязного списка ребер. Входными данными является половина ребра, начало которого находится в ограничивающей рамке.
Я знаю, что две точки смежны на выпуклой оболочке тогда и только тогда, когда они имеют бесконечно длинное ребро Вороного.
Если у вас есть ограничивающая рамка, достаточно большая, чтобы только бесконечные ячейки имели ограничивающие края, задача не кажется сложной. Переберите ограничивающие ребра, для каждого из них пройдите вперед и назад, чтобы найти первые не ограничивающие ребра F и B. Отметьте текущую и все граничные ребра, найденные во время хода, как used. Ребра F и B были бы бесконечными, если бы коробка не существовала. Таким образом, они касаются граней (fF и fB), чьи "центры" являются частью выпуклой оболочки (текущая грань C), а поперечное ребро C-to-F является частью выпуклой оболочки. Возьмите грань fF и выполните итерацию от близнеца F вперед, чтобы найти следующее не ограничивающее ребро, скажем, F1. Если он равен 'B'-близнецу (или его ограничивающие ребра были used), мы закончили. Если нет, перейдите к следующему соседу ('fF1').
Я считаю, что можно вычислить выпуклую оболочку диаграммы Вороного за время O(n).
В случае заданной диаграммы Вороного и вершины, которая должна находиться в CH, вы можете перебирать ячейки диаграммы Вороного и расширять выпуклую оболочку так же, как это делается в алгоритме сканирования Грама, но другим способом.
Здесь не хватает только одной теории, смотрите дальше...
Согласно Computational Geometry by Springer the M4 book, Теорема 7.4: точка q является вершиной Vor(P) тогда и только тогда, когда ее наибольшая пустая окружность C_p(q) содержит три или более узлов на своей границе. Это означает, что сайты, которые необходимо проверять на каждой итерации, выполняются за O (1), а это означает, что вам нужно перебирать только O (n) сайтов.
Согласно теореме 7.3 число вершин в диаграмме Вороного множества из n точек на плоскости не превосходит 2n-5 (линейный порядок).
Поэтому можно вычислить СН диаграммы Вороного за время O(n).
