Нижние оценки точности. Нижние оценки сложности для задачи сортировки, построения выпуклой оболочки

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

В завершение мы рассмотрим задачу построения выпуклой оболочки для конечного множества точек в двумерном Евклидовом пространстве. Эта задача хорошо исследована, является составной частью большого числа задач вычислительной геометрии, и имеет много приложений в области распознавания образов, при обработке изображений, в математической статистике, в задачах раскроя материалов и т.п. С другой стороны задача построения выпуклой оболочки множества тесно связана с задачей сортировки данных. Ранее было показано, что задача сортировки за линейное время сводится к задаче построения выпуклой оболочки множества, в силу чего нижняя оценка времени для задачи построения выпуклой оболочки на множестве из n точек составляет W(nlog n). Построение выпуклой оболочки является прекрасным примером задачи, когда идеи, полученные на одном классе задач переносятся на другой класс и дают при этом хорошие результаты. Рассмотрим некоторые подходы к решению задачи в двумерной области, изложенные в [4,5,26] Определение 1. Множество S Í E2, будет называться выпуклым, если для любой пары точек 1 p и 2 p из S отрезок с концами 1 p и 2 p целиком принадлежит S

.

Определение 2. Точка p выпуклого множества S называется крайней, если не существует пары точек 1 p и 2 p, из S таких, что 1 2 p =ap + (1-a) p, 0 <a <1, (т.е. p не является внутренней точкой отрезка с концами 1 p и 2 p).

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

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

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

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

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

Продолжение 8

Теорема[5]. Точка p не является крайней точкой множества S только тогда, когда она лежит в некотором треугольнике, вершины которого принадлежат S, но сама она не является вершиной этого треугольника. Согласно этой теореме достаточно перебрать все тройки вершин, принадлежащих S, с последующим удалением всех точек, лежащих внутри треугольника, задаваемого этой тройкой вершин. Поскольку число различных треугольников равно числу сочетаний 3 n C, а для каждого из рассматриваемых треугольников за константное время можно определить, лежит ли некоторая точка внутри треугольника, вся процедура перебора занимает O(n4) времени. Вторая задача решается сортировкой и требует O(nlog n) времени При таком подходе верхняя оценка сильно отличается от нижней. Неэффективность предложенного алгоритма связана, прежде всего, с избыточным перебором. Алгоритм построен на исключении из множества S точек, которые не входят в выпуклую оболочку, при этом перебор соответствующих точек ведется случайным образом, информация, которая связана с одной и той же точкой вычисляется многократно (одна и та же вершина может лежать в большом числе треугольников). Поскольку полученная после первого шага последовательность крайних точек никак не связана с порядком их перечисления в выпуклой оболочке, необходим второй шаг. Все описанные ниже алгоритмы задают определенный порядок перечисления кандидатов на включение в выпуклую оболочку, но при этом используют различные свойства выпуклой оболочки.