5.2. Задача построения выпуклой оболочки

В завершение мы рассмотрим задачу построения выпуклой оболочки для конечного множества точек в двумерном Евклидовом пространстве. Эта задача хорошо исследована, является составной частью большого числа задач вычислительной геометрии, и имеет много приложений в области распознавания образов, при обработке изображений, в математической статистике, в задачах раскроя материалов и т.п. С другой стороны задача построения выпуклой оболочки множества тесно связана с задачей сортировки данных. Ранее было показано, что задача сортировки за линейное время сводится к задаче построения выпуклой оболочки множества, в силу чего нижняя оценка времени для задачи построения выпуклой оболочки на множестве из точек составляет. Построение выпуклой оболочки является прекрасным примером задачи, когда идеи, полученные на одном классе задач переносятся на другой класс и дают при этом хорошие результаты. Рассмотрим некоторые подходы к решению задачи в двумерной области, изложенные в [4,5,26]

Определение 1. Множество, будет называться выпуклым, если для любой пары точекиизотрезок с концамиицеликом принадлежит.

Определение 2. Точкавыпуклого множестваназывается крайней, если не существует пары точеки, изтаких, что,(т.е.не является внутренней точкой отрезка с концамии).

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

Выпуклая оболочка для конечного множества точек является выпуклым многоугольником, содержащим все его точки. Очевидно, что множество крайних точек изявляется наименьшим подмножеством, выпуклая оболочка которого, является выпуклой оболочкой множества: (). В связи с этим напрашивается выполнение следующих процедур в алгоритме построения выпуклой оболочки:

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

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

Для решения первой задачи можно использовать следующий результат.

Теорема[5]. Точка не является крайней точкой множестватолько тогда, когда она лежит в некотором треугольнике, вершины которого принадлежат S, но сама она не является вершиной этого треугольника.

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

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

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