ВЫПУКЛЫЕ ОБОЛОЧКИ

 

Задача вычисления (построения) выпуклой оболочки не только является центральной в целом ряде приложений, но и позволяет разрешить ряд вопросов вычислительной геометрии, на первый взгляд не связанных с ней. Построение выпуклой оболочки конечного множества точек, особенно в случае точек на плоскости, уже довольно широко и глубоко исследовано и имеет приложения, например, в распознавании образов [Akl, Toussaint (1978); Duda, Hart (1973)], обработке изображений [Rosenfeld (1969)], а также в задаче раскроя и компоновки материала [Freeman (1974); Sklansky (1972); Freeman-Shapira (1975)].

Основные понятия и идеи

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

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

Ещё одним понятием, которое нам понадобится, является понятие крайней точки. Точка выпуклого множества S называется крайней, если не существует пары точек a, b Î S таких, что p лежит на открытом отрезке ab. Множество E крайних точек S в точности совпадает с множеством вершин выпуклой оболочки S. Используя это свойство, мы приходим к основной идее алгоритма поиска:

1. Определить крайние точки.

2. Упорядочить эти точки так, чтобы они образовывали выпуклый многоугольник.

Необходима теорема, которая позволит нам проверять, является ли некоторая точка крайней.

Теорема 1. Точка р не является крайней плоского выпуклого множества S только тогда, когда она лежит в некотором треугольнике, вершинами которого являются точки из S, но сама она не является вершиной этого треугольника (рис. 23).

 

Рис. 23. Точка р не является крайней, так как она находится внутри треугольника (p₁p₂p₃)

 

Эта теорема дает идею для алгоритма удаления точек, не являющихся крайними. Имеется О(N ³) треугольников, определяемых N точками множества S. Проверка принадлежности точки заданному треугольнику может быть выполнена за некоторое постоянное число операций, так что за время О (N ³) можно определить, является ли конкретная точка крайней. Повторение этой процедуры для всех N точек множества S потребует времени O(N ⁴). Хотя наш алгоритм является чрезвычайно неэффективным, он очень прост в идейном плане и показывает, что крайние точки могут быть определены за конечное число шагов.

Мы затратили время О(N⁴) только на определение крайних точек, которые должны быть как-то упорядочены, чтобы образовать выпуклую оболочку. Смысл этого порядка раскрывается следующими теоремами.

Теорема 3.5. Луч, выходящий из внутренней точки ограниченной выпуклой фигуры F, пересекает границу F в точности в одной точке.

Теорема 3.6. Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла относительно любой внутренней точки.

Если даны крайние точки некоторого множества, то его выпуклую оболочку можно найти, выбрав точку q, про которую известно, что она является внутренней точкой оболочки, и упорядочив затем крайние точки в соответствии с полярным углом относительно q. Сортировку можно провести за O(N log N) шагов. Таким образом, мы показали, что задача поиска выпуклой оболочки может быть решена за время O(N⁴).