Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 72

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 66 67 68 69 70 71 < 72 > 73 74 75 76 77 78 .. 180 >> Следующая


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







у'

четырьмя краш

же [Bentley, Kung, Schkolnick, Thompson (1978)]). Суть имеющегося сходства заключается в том, что как максимумы, так и выпуклая оболочка являются представлениями «границы» множества S, хотя первые дают неполное представление этой границы. В частности, если задано некоторое множество точек S, то можно поставить столько задач о максимумах, сколько имеется ортантов в пространстве Еа (т. е. 2а задач; см. рис. 4.3, где для случая d = 2 имеются четыре ортанта, называемых квадрантами). Каждая из этих задач может быть получена путем приписывания одного из знаков « + » или «—» каждой из координат точек множества S (исходной формулировке задачи соответствует комбинация знаков (++ ... +))• Нужную нам взаимосвязь между задачами выражает следующая теорема:

Теорема 4.7. Вершина р выпуклой оболочки множества S является максимумом по крайней мере при одном присваивании знаков координатам точек множества S.

7 Зак. 1075

194 Г л. 4. Выпуклые оболочки: расширения и приложения

Доказательство. Предположим противное, а именно что имеется вершина выпуклой оболочки р, не являющаяся максимумом ни при каком присваивании знаков координатам точек. Поместим начало системы координат в точку р и рассмотрим все 2d ортантов пространства Ed. Так как точка не является максимумом ни при одном присваивании знаков координатам точек множества S, то в каждом ортанте имеется по крайней мере одна точка множества S, отличная от р. Обозначим множество этих точек через 5*. Очевидно, что conv(S*) содержит внутри точку р и, следовательно, conv(5*) ^conv(S), что противоречит предположению о принадлежности точки р границе выпуклой оболочки.

Далее в этом разделе мы еще вернемся к этой интересной взаимосвязи. Прежде чем переходить к описанию алгоритма решения задачи о максимумах, уместно оценить ее сложность, получив нижнюю оценку для времени работы любого алгоритма отыскания максимумов в рамках модели деревьев вычислений. В частности, приводимое ниже рассуждение относится к несколько более слабому случаю модели линейных деревьев решений, известному как модель деревьев сравнений, хотя область применения полученных результатов можно расширить и на более сильный случай. (В модели деревьев сравнений число аргументов линейной функции ограничено двумя переменными.) Как это уже было в случае задачи построения выпуклой оболочки (разд. 3.1), будем искать нижнюю оценку для случая двумерного пространства. Очевидно, что поскольку любую задачу р максимумах в можно рассматривать как задачу в Ed, то такая нижняя оценка будет справедлива для пространств любой размерности (к сожалению, неизвестно, насколько эта оценка точна для й>Ъ). Нет ничего удивительного в том, что для того, чтобы получить нетривиальную нижнюю оценку сложности, мы прибегнем, как это часто делается для нижних оценок небольшой сложности, к уже знакомому сведению задач:

СОРТИРОВКА ос„ МАКСИМУМЫ.

Пусть s4- — алгоритм, описанный с помощью дерева сравнений Т (см. разд. 1.4), о котором утверждается, что он решает любую задачу о максимумах для множества из N точек, заданных на плоскости. Выполнение алгоритма s4- при решении любой конкретной индивидуальной задачи соответствует прохождению в дереве Т пути из его корня до некоторого листа. Сведение от задачи сортировки выполняется следующим образом. Пусть заданы N действительных чисел a'i,.v2, Уц. Образуем множество точек на плоскости, положив 5 = {рг. t = 1, . . . , W; р,- = = (Xi, у,), xt + yL = const}. Это можно сделать за линейное

4.1. Расширения и варианты

195

время. Условие xt + г/,- = const для i = 1, .... N эквивалентно следующему:

х1<х1^-у,>у1. (4.7)

Заметим, что при таком способе построения множества S каждый элемент (Xi, г/,) является максимальным. Для того чтобы определить, что (х,, у,) — максимум, алгоритм зФ должен уметь устанавливать тот факт, что «не существует такого / ф I, что xi < х,- и yi < г/у». Но это эквивалентно следующему утверждению: «для всех / ф I либо xt > Xj, либо y-t > у,-, т. е. либо xi > л;,-, либо xi<LXj» (в соответствии с (4.7)). Другими словами, для каждой пары {Xi, Xj] известен относительный порядок её элементов, т. е. каждому листу дерева Т соответствует единственное упорядоченное множество {х\, х2, ¦ ¦ ¦, xN}, что дает решение задачи сортировки. Таким образом, имеет место следующая теорема:

Теорема 4.8 tKung, Luccio, Preparata (1975)]. В рамках модели деревьев сравнений любой алгоритм, решающий задачу о максимумах для двумерного случая, имеет сложность Q{N\ogN).

Теперь, имея для сложности алгоритма оценку снизу, рассмотрим вопрос разработки алгоритмов решения задачи о максимумах. Эта задача предоставляет нам великолепную возможность сравнить относительные достоинства и эффективность двух основных парадигм вычислительной геометрии: «разделяй и властвуй» и заметания по одному из измерений (см. разд. 1.2.2).

Начнем с последней. Первым шагом в методе заметания является сортировка всех точек множества S в соответствии со значением выбранной координаты, например xd. Эта координата становится измерением, по которому производится заметание. В соответствии с терминологией, введенной в разд. 1.2.2, «список точек событий» — это очередь Q, содержащая точки множества в порядке уменьшения координаты xd. Организация структуры, представляющей «статус заметающего сечения», будет рассмотрена позже. Запись р обозначает, что существует точка q е U такая, что р ^q. Теперь можно дать набросок следующего общего алгоритма:
Предыдущая << 1 .. 66 67 68 69 70 71 < 72 > 73 74 75 76 77 78 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed