Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Проиллюстрируем теперь взаимосвязь между задачей о максимумах и задачей о построении выпуклой оболочки (см. так-
у'
четырьмя краш
же [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. Теперь можно дать набросок следующего общего алгоритма: