Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Прежде чем переходить к описанию алгоритмов, уместно дать формальную постановку задачи и указать на важный вопрос относительно нижних оценок сложности этой задачи. Так как алгоритмы построения выпуклой оболочки имеют дело с границей этой выпуклой оболочки, то мы будем обозначать символом CH(L) границу выпуклой оболочки conv(L). Заметим, однако, что в соответствии с общепринятой практикой как conv(L), так и CH(L) будут называться «выпуклой оболочкой».
¦') Это следует из теоремы Штейница. См. [Griinbaum, (1967), р. 235].
для четных d,
нечетных d.
(3.3)
120
Гл. 3. Выпуклые оболочки: основные алгоритмы
3.2. Постановка задачи и нижние оценки сложности
Начнем с формулировки двух основных вариантов задачи построения выпуклой оболочки.
Задача В01 (ВЫПУКЛАЯ ОБОЛОЧКА). В Е" задано множество 5, содержащее N точек. Требуется построить их выпуклую оболочку (т. е. полное описание границы СН(5)).
Задача В02 (КРАЙНИЕ ТОЧКИ). В Еа задано множество 5, содержащее N точек. Требуется определить те из них, которые являются вершинами выпуклой оболочки conv(S).
Должно быть понятно, что задача В01 асимптотически является по крайней мере такой же сложной, как и задача В02, так как решение задачи В01 превращается в решение задачи В02, если мы просто скопируем множество вершин, порождаемое в результате решения первой задачи, представив его в виде неупорядоченного списка точек. То есть одна задача преобразуется в другую, или
КРАЙНИЕ ТОЧКИ ос„ ВЫПУКЛАЯ ОБОЛОЧКА.
Естественно задать вопрос, является ли первая задача асимптотически более простой, чем вторая, или они имеют в действительности одинаковую сложность. Так как любая совокупность точек в двумерном пространстве тривиальным образом вкладывается в пространство Еа для d > 2, то любой результат для нижней оценки, полученный для d = 2, заведомо остается справедливым для d > 2. Поэтому в дальнейшем обсуждении мы будем рассматривать двумерные варианты задач В01 и В02.
Начнем с рассмотрения задачи В01 о выпуклой оболочке на плоскости. То, что вершины многоугольника, являющегося выпуклой оболочкой, следуют в определенном порядке (в действительности мы можем говорить об упорядоченной выпуклой оболочке), указывает на естественную связь с задачей сортировки. В самом деле, следующая теорема устанавливает тот факт, что любой алгоритм решения задачи В01 должен быть способен выполнять сортировку.
Теорема 3.2. Задача сортировки сводима за линейное время к задаче построения выпуклой оболочки, и, следовательно, для нахождения упорядоченной выпуклой оболочки N точек на плоскости требуется время Q(N\ogN).
Доказательство. Мы продемонстрируем процедуру сведения, а сформулированное в теореме заключение является следствием утверждения 1 из разд. 1.4. Пусть заданы N положительных действительных чисел хи .. ., xN. Необходимо показать, как
3.2. Постановка задачи и нижние оценки сложности
121
можно использовать алгоритм построения выпуклой оболочки для сортировки этих чисел, чтобы при этом дополнительные затраты линейно зависели от количества чисел. Поставим в соответствие числу xi точку (xt, х]) и присвоим ей номер I (рис. 3.1). Все эти точки лежат на параболе у = х2. Выпуклая оболочка этого множества точек, представленная в стандартном виде, будет состоять из списка точек множества, упорядоченного по значению абсциссы. Один просмотр этого списка позволяет прочитать в нужном по-
Парабола у =
с доказатель-
рядке значения Xi1).
Так как для процедуры сведения используются только арифметические операции, то теорема 3.2 остается справедливой во многих вычислительных моделях. А именно в моделях, допускающих умножение, и в которых время, необходимое для сортировки, равно Q(NlogN). Как указывалось ранее, теорема 3.2 применима в пространствах любой размерности, большей I2).
Если взглянуть на задачу В02 о крайних точках, то сразу же становится ясно, что здесь не возникает никаких элементарных соображений, подобных приведенным выше. В действительности эта задача на протяжении некоторого времени оставалась нерешенной. Первым прорывом явилась работа А. Яо [Yao (1981)], а окончательный ответ был получен в результате соединения мощного метода алгебраических деревьев решений Бен-Ора (см. разд. 1.4) с недавним результатом Стили и Яо [Steele, Yao (1982)].
Следуя привычному ходу мысли, рассмотрим задачу распознавания, связанную с В02, которая формулируется следующим образом.
Задача ВОЗ (ПРОВЕРКА КРАЙНОСТИ ТОЧЕК ПЛОСКОСТИ). На плоскости заданы N точек. Определить, являются ли они вершинами своей собственной выпуклой оболочки?
') Шеймос первоначально доказал эту теорему, отображая числа Xi на единичную окружность. Отображение на параболу, предложенное С. Эйзенста-том, является более предпочтительным, так как оно требует лишь операций рациональной арифметики.
2) Выпуклой оболочкой множества точек в пространстве размерности 1 наименьший содержащий их интервал. Этот интервал может быть линейное время.
122
Г л. 3. Выпуклые оболочки: основные алгоритмы
