Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Если вспомнить нижнюю оценку, обсуждавшуюся в разд. 3.2, то видно, что этот простой и изящный алгоритм имеет оптимальное время выполнения. Однако имеется одно обстоятельство, которое может вызвать некоторое беспокойство у читателя,— это использование полярных координат. В самом деле, это предполагает выполнение преобразования координат, что может быть затруднительным в системах с ограниченным набором прими-5*
132
Гл. 3. Выпуклые
основные алгоритл
тивных операций. Как это обычно случается, ряд исследователей обратили внимание на это обстоятельство и предложили решения, позволяющие избежать его. Мы коротко опишем метод, предложенный Эндрью (Andrew (1979)]. Другой подход, также заслуживающий внимания, был предложен Эклом и Тус-сэном (Akl, Toussaint (1978)].
Пусть на плоскости задано множество из N точек. Определим сначала его левую и правую крайние точки / и г (рис. 3.7) и построим прямую, проходящую через эти точки. Оставшиеся точки разбиваются на два подмножества (нижнее и верхнее)
Рис. 3.7. Левая и правая крайние точки определяют разбиение множества на два подмножества.
в зависимости от того, по какую сторону от прямой они располагаются — ниже или выше прямой. Нижнее подмножество порождает ломаную (нижнюю оболочку, или Н-оболочку), монотонную относительно оси х. Точно так же верхнее подмножество порождает аналогичную ломаную (верхнюю оболочку, или В-оболочку), а соединение этих двух ломаных дает выпуклую оболочку исходного множества.
Рассмотрим построение верхней оболочки. Точки упорядочиваются в соответствии с возрастанием абсциссы, и к полученной последовательности применяется метод обхода Грэхема. При таком подходе отпадает необходимость в тригонометрических операциях. Заметим, однако, что предлагаемый подход есть не что иное, как частный случай применения исходного метода Грэхема, когда точка q, совпадающая с началом координат, выбирается бесконечно удаленной в отрицательном направлении (-со) по оси у, так что в этом случае упорядоченность по абсциссе совпадает с упорядоченностью по полярному углу.
Несмотря на то что, как было показано, алгоритм Грэхема является оптимальным, по-прежнему имеется много причин для продолжения исследования задачи о выпуклой оболочке.
1. Рассмотренный алгоритм является оптимальным в худшем случае, но мы, однако, не изучили его поведение в среднем.
2. Так как алгоритм основывается на теореме 3.6, применимой только в случае плоскости, алгоритм не имеет обобщения на случай пространств более высокой размерности.
Верхнее подмножество
Нижнее подмножество
3.3. Алгоритм построения выпуклой оболочки
133
3. Алгоритм не является открытым алгоритмом ¦), так как все точки множества должны быть известны до начала работы алгоритма.
4. При возможности параллельной обработки более предпочтительным является рекурсивный алгоритм, допускающий разбиение исходной задачи и данных на меньшие подзадачи.
Прежде чем закончить этот раздел, отметим, что метод Грэхема явным образом использует сортировку. Вряд ли можно найти более прямую связь этой задачи с задачей сортировки. Аналогично тому, как исследование сортировки показало, что не существует одного алгоритма, лучшего во всех случаях, мы увидим, что то же самое справедливо и для задачи построения выпуклой оболочки. Давайте продолжим исследование комбинаторной геометрии в поисках идей, способных привести к иным алгоритмам построения выпуклой оболочки.
3.3.3. Обход методом Джарвиса
Многоугольник с одинаковым успехом можно задать упорядоченным множеством как его ребер, так и его вершин. В задаче о выпуклой оболочке мы до сих пор обращали внимание главным образом на изолированные крайние точки. А что если вместо этого попытаться определить ребра выпуклой оболочки, приведет ли такой подход к созданию практически пригодного алгоритма? Если задано множество точек, то довольно трудно быстро определить, является или нет некоторая точка крайней. Однако если даны две точки, то непосредственно можно проверить, является или нет соединяющий их отрезок ребром выпуклой оболочки.
Теорема 3.8. Отрезок I, определяемый двумя точками, является ребром выпуклой оболочки тогда и только тогда, когда все другие точки заданного множества лежат на I или с одной стороны от него [Stoer, Witzgall (1970), теорема 2.4.7]. (См. рис. 3.8.)
N точек определяют (^Q = 0(N2) прямых. Для каждой из
этих прямых можно, используя формулу (3.4), определить за линейное время положение остальных N — 2 точек относительно этой прямой и тем самым проверить, удовлетворяет или нет прямая условиям теоремы 3.8. Таким образом, за время 0(N3) можно найти все пары точек, определяющих ребра выпуклой оболочки. Не надо затем большого труда, чтобы расположить эти точки в виде списка последовательных вершин оболочки.
') См. определение открытого алгоритма в разд. 3.3.6. В оригинале «оп-Нпе». — Прим. перев.
134
Гл. 3. Выпуклые оболочки: основные алгоритмы
Джарвис заметил, что этот алгоритм можно улучшить, если учесть следующий факт. Если установлено, что отрезок pq является ребром оболочки, то должно существовать другое ребро с концом в точке q (Jarvis (1973)]. В его работе показано, как использовать этот факт, чтобы уменьшить требуемое время до 0(№). Кроме того, в ней содержится ряд других идей, заслуживающих подробного обсуждения. Здесь будет рассмотрен вариант, включающий изменения, предложенные Эклом [Akl (1979)] и устраняющие небольшие неточности.
