Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
3.3.5. Алгоритмы типа «разделяй и властвуй»
Описанный в предыдущем разделе метод БЫСТРОБОЛ не только прост в реализации, но и является попыткой достигнуть одну из целей, сформулированных в конце разд. 3.3.2 (цель 4 — возможность распараллеливания алгоритма). Действительно, алгоритм разбивает исходную задачу на две подзадачи, каждая из которых может решаться независимо от другой, и, следовательно, они могут решаться одновременно при возможности параллельной обработки. Кроме того, объединение результатов решения двух подзадач — так называемый шаг «слияния» — представляет очень простую конкатенацию двух результатов. К сожалению, эта простота является платой за невозможность правильно управлять размерами двух подзадач, на которые разбивается исходная задача, и тем самым гарантировать приемлемое поведение алгоритма в худшем случае.
Следовательно, несмотря на то что он представляет метод «разделяй и властвуй», являющийся фундаментальным в области разработки алгоритмов, БЫСТРОБОЛ имеет очевидные недостатки. В самом деле, подход «разделяй и властвуй» основан на принципе сбалансированности i[Aho, Hopcraft, Ullman (1974), с. 751)], предполагающем, что вычислительная задача должна разбиваться на подзадачи примерно одинакового размера.
') Ссылка дается на русское издание. — Прим. перев.
Предположим, при решении задачи построения выпуклой оболочки, исходное множество точек было разбито на две части Si и 52, каждая из которых содержит половину точек исходного множества. Если теперь рекурсивным образом найдены отдельно CH(Sj) и CH(S2), то каковы дополнительные затраты, необходимые для построения CH(SiU52), т.е. выпуклой оболочки исходного множества? Для ответа на этот вопрос можно воспользоваться следующим соотношением:
CH(S, U S2) = CH(CH(S,) U CH(S2)). (3.7)
Хотя при первом взгляде на соотношение (3.7) кажется, что такой способ требует больших затрат, чем прямой способ построения выпуклой оболочки, решающее соображение состоит в том,
Рис. 3.11. Построение выпуклой оболочки методом «разделяй и властвуй». Разбив множество S на два подмножества и построив рекурсивно выпуклые оболочки этих подмножеств, можно свести исходную задачу к построению выпуклой оболочки объединения двух выпуклых многоугольников.
что CH(Si) и СН(52) — это не просто неупорядоченные множества точек, а выпуклые многоугольники (рис. 3.11).
Задача В04 (ВЫПУКЛАЯ ОБОЛОЧКА ОБЪЕДИНЕНИЯ ВЫПУКЛЫХ МНОГОУГОЛЬНИКОВ). Заданы два выпуклых многоугольника Р\ и Р2. Найти выпуклую оболочку их объединения.
Помимо того что эта задача интересна сама по себе, она важна и в силу того, что представляет собой шаг слияния процедуры «разделяй и властвуй» и, таким образом, дает фундаментальное средство для решения геометрических задач. Нельзя надеяться, что окончательный алгоритм будет эффективным, до тех пор, пока решения подзадач не могут быть быстро объединены.
procedure СЛИ0Б0Л(5) 1. Если |5| ^ k0 (ko — некоторое небольшое целое число), то построить выпуклую оболочку одним из прямых методов и остановиться; иначе перейти к шагу 2.
3.3. Алгоритм построения выпуклой оболочки
141
2. Разбить исходное множество S произвольным образом на два примерно равных по мощности подмножества Si и S2.
3. Рекурсивно найти выпуклые оболочки Si и S2.
4. Слить (соединить) две получившиеся оболочки вместе, образуя CH(S).
Обозначим символом U (N) время, необходимое для нахождения выпуклой оболочки объединения двух выпуклых многоугольников, каждый из которых имеет N/2 вершин. Если T(N) — время, необходимое для нахождения выпуклой оболочки множества из N точек, то, применяя соотношение (3.7), получаем
T{N)^2T(N/2) + U(N). (3.8)
Следующий алгоритм «слияния» предложен М. Шеймосом [Shamos (1978)]:
procedure ОБОЛОЧКА-ОБЪЕДИНЕНИЯ-ВЫПУКЛЫХ-МНОГОУГОЛЬНИКОВ(Рь Р2) 1. Найти некоторую внутреннюю точку р многоугольника Pi. (Например, центроид трех любых вершин Р\. Такая точка р будет внутренней точкой CH(Pi\j Р2)¦)
Рис. 3.12. Точка р находится внутри многоугольника Р2. Так как точка р одновременно находится внутри обоих многоугольников Р, и Р2, то их вершины упорядочены по значению полярного угла точки р. Слияние двух упорядоченных множеств вершин можно выполнить за линейное время.
2. Определить, является ли р внутренней точкой Р2. Это может быть сделано за время O(N) методом, описанным в разд. 2.2.1. Если р не является внутренней точкой Р2, перейти к шагу 4.
3. р является внутренней точкой Р2 (рис. 3.12). По теореме 3.6 вершины как Pi, так и Р2 оказываются упорядоченными в соответствии со значением полярного угла относительно точки р. За время O(N) можно получить упорядоченный список вершин как Ри так и Р2 путем слияния списков вершин этих многоугольников. Перейти к шагу 5.
142
Гл. 3. Выпуклые оболочки: основные алгоритмы
4. р не является внутренней точкой Р2 (рис 3.13). Если смотреть из точки р, то многоугольник Р2 лежит в клине с уголом разворота меньшим или равным я. Этот клин определяется двумя вершинами и и v многоугольника Р2, которые могут быть найдены за линейное время за один обход вершин многоугольника Р2. / Эти вершины разбивают границу Р2 на две цепи вершин/ являющиеся монотонными относительно
