Выпуклые оболочки / Алгоритм ЛИ

Введение

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

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

Определение:

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

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

Подход, основанный на поиске нижних оценок, в данной ситуации неприемлем даже для случая упорядоченной оболочки, так что следует довольствоваться тривиальной нижней оценкой . Поэтому вполне естественно искать алгоритмы, имеющие в худшем случае сложность, меньшую . И ряд таких алгоритмов, каждый со сложностью , был предложен. Некоторые из них оказываются неработоспособными в некоторых очень частных случаях [Sklansky (1972); Shamos (1975)] , но другие алгоритмы правильно решают поставленную задачу. Среди последних следует упомянуть довольно сложный алгоритм Маккаллума – Эйвиса [McCallum, Avis (1979)], использующий два стека. Впоследствии были предложены два новых алгоритма, использующие один стек, - первый Ли [Lee(1983)], а второй Грэхемом и Яо [Graham, Yao 1983]. Рассмотрим вариант алгоритма Ли.

Теоретические сведения

Самая левая точка – точка, которая при минимальной абсциссе имеет также максимальную ординату.

Самая правая точка - точка, которая при максимальной абсциссе имеет также минимальную ординату.

Точка находится слева относительно ориентированной прямой:

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

Упорядоченная тройка вершин называется правым поворотом, если находится справа от прямой, проходящей через и с учетом направления от к ; в противном случае она называется левым поворотом

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

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

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

Алгоритм Ли (построение выпуклой оболочки полигона)

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

Пусть - самая правая вершина. Ясно, что и являются граничными точками выпуклой оболочки многоугольника . Кроме того, они разбивают последовательность вершин многоугольника на две цепи: одна от до , другая от до . Достаточно рассмотреть построение выпуклой оболочки лишь для цепи , которую согласно использовавшейся ранее терминологии, будем называть верхней оболочкой. Пусть подпоследовательность последовательности , у которой и , - искомая выпуклая оболочка многоугольника. Каждое из ребер можно рассматривать как ”крышку” “кармана” , где карман - это подцепочка последовательности , первой и последней вершинами которой являются и соответственно.

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

Предположим, что граница многоугольника просмотрена от вершины до

и вершина является критической. Соответствующая ситуация показана на рис.2., где карман закрыт крышкой .

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

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

2. Вершина находится слева от . В этом случае в дополнение к предыдущим определим еще одну область , показанную на рис. 4.10 (b).

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

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

1. Вершина принадлежит области . В этом случае граница многоугольника заходит в карман. Будем продвигаться по границе до тех пор, пока не достигнем первого

ребра границы, одна из вершин которого находится вне кармана, т.е. в области

(рис.4.(a)). Так как многоугольник простой, а карман и его крышка также образуют простой многоугольник, то, согласно теореме о жордановой клетке, граница многоугольника обязательно пересечет крышку кармана. Далее обрабатываем , как вершину в случае, когда принадлежит области , рассматриваемом ниже.

2. Вершина принадлежит области . Вершина является критической. Ищется опорная прямая из вершины к цепи . Если эта прямая содержит , то вершины удаляются, а берется в качестве новой (рис. 4.(b)). Ясно, что является вершиной выпуклой оболочки (критической точкой), так как она является внешней по отношению к текущей оболочке . Проведение опорной прямой эквивалентно построению .

3. Вершина принадлежит области . Вершина является критической, и она берется в качестве . Действительно (рис. 4(с)), является внешней по отношению к текущей оболочке , и так как она находится справа от прямой,

проходящей через и (и ориентированной в направлении от к ), то угол является выпуклым (при этом (рис.4.(с)) иллюстрирует случай, соответствующий рис.3.(b).).

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

Предыдущее обсуждение включает доказательство корректности любой реализации, в которой обработка случаев 1 – 4 производится указанным выше способом. Наиболее подходящими структурами данных являются: (1) очередь , содержащая последовательность ; (2) стек Q для хранения последовательности - в виду того, что для вставки и удаления точек выпуклой оболочки используется механизм “последний вошел – первый вышел”, где - фиктивная вершина, имеющая ту же абсциссу, что и , но меньшую ординату и обеспечивающая единообразие обработки. Как было сказано выше, - это вершина на границе многоугольника , непосредственно предшествующая вершине , а вершина - текущая вершина. Кроме того, наряду с обычным использованием операции , означающей: “ЗАТОЛКНУТЬ в ”, операция ВЫТОЛКНУТЬ означает: ”; игнорировать ”; обозначает вершину, находящуюся на вершине стека, а ПЕРЕДНИЙ() обозначает первый элемент очереди .

procedure ОБОЛОЧКА_МНОГОУГОЛЬНИКА

(p₁,…,p_M)

1. begin ;

2. ;

3. ;

4. while do

5. begin ;

6. if((q_i-1q_iv) – правый поворот)

/*области 1, 3, 4*/ then

7. if ((uq_iv) – правый поворот /* области 3, 4*/)) then

8. if ((q_Mq_iv) – правый поворот)

/*область 3*/ then

9. else /*область 4*/

10. while(ПЕРЕДНИЙ(P) находится слева от или на нем) do

ВЫТОЛКНУТЬ P

11. else /*область 1*/

12. while(ПЕРЕДНИЙ(P) находится слева от или на нем ) do

ВЫТОЛКНУТЬ P

13. else /*область 2*/

14. begin while ((q_i-1q_iv) – левый поворот)

do ВЫТОЛКНУТЬ Q;

15.

end

end

end.

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

Теорема. Выпуклая оболочка простого многоугольника с вершинами может быть построена за оптимальное время при использовании памяти объемом .