Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
и q i ,Nl+r ч лежат слева от направленного отрезка p2ip2i+2; но
2 ( i)
мы знаем, что имеется только одна точка в множестве [ро, . . . ..., p2N-\}, обладающая этим свойством, и этой точкой является p2i+\. Таким образом, <7__ь„,,г. =<7__ь„,,.=/?,,,.. Если это
ni г' + о "г г'+*•) имеет место для всех значений i, то эти две перестановки совпадают, что противоречит предположению.
Поэтому существует такое /, что Л(я1)[/] и Л(я2)[/] имеют противоположные знаки. Заметим теперь, что z(m) и г(я2) являются различными точками в Е4К, и рассмотрим кривую р в EiN, соединяющую эти точки. Точка z, двигающаяся по р из г(я]) в г(я2), описывает непрерывную деформацию на плоскости конфигурации, соответствующей яь в конфигурацию, соответствующую я2, при этом А(л\) преобразуется в Л(я2). Так как А {п\) [/) -А(п2) [/] <0, то, согласно теореме о промежуточном значении, на кривой р существует точка z* такая, что в соответствующей конфигурации три точки становятся коллинеарными (т. е. треугольник с вершинами в этих точках имеет нулевую площадь), и поэтому не более чем (2А/—1) точек являются крайними. Это доказывает, что при перемещении из г(яО в г(я2) мы должны выходить из W, так что z(n\) и г(л2) принадлежат различным компонентам W. Так как это справедливо при произвольном выборе Я1 и я2, то отсюда следует, что #(№):=гЛП.
С учетом теоремы Бен-Ора имеем:
3.3. Алгоритм построения выпуклой оболочы
125
Теорема 3.3. В рамках модели алгебраических деревьев вычислений фиксированного порядка для определения крайних точек множества из N точек на плоскости требуется Q (Л/ log TV) операций.
Доказательство. В нашем случае m = AN и #(№) ^ N1. Согласно теореме Бен-Ора, необходимо (log #(W) — ni) ^ ^ (log jV! — AN)= Q (Л/log Л/) операций.
На этом заканчивается наше обсуждение сложности задачи. Прежде чем закончить эту тему, заметим, что двумерные варианты как задачи об упорядоченной выпуклой оболочке В01, так и задачи о крайних точках В02 имеют тесную связь с задачей сортировки. Действительно, задача В01 явным образом связана с ней посредством прямого сведения, в то время как связь В02 осуществляется через мощность симметрической группы. Эта связь является довольно глубокой, и в дальнейшем в этой главе мы будем часто обращаться к ней.
Теперь мы переходим к описанию алгоритмов построения выпуклой оболочки.
3.3. Алгоритм построения выпуклой оболочки на плоскости
3.3.1. Предварительная разработка алгоритма построения выпуклой оболочки
Теперь мы должны, опираясь на неконструктивное по своей сути определение 3.4, получить математические результаты, ведущие к эффективным алгоритмам. В работах такого рода принято представлять последовательность хорошо обоснованных и «отполированных» результатов, но сделать так здесь означало бы лишь совсем немного раскрыть процесс разработки алгоритмов, являющийся стержнем вычислительной геометрии. Поэтому мы начинаем с обсуждения некоторых малопродуктивных подходов.
Определение 3.6. Точка р выпуклого множества 5 называется крайней, если не существует пары точек а,Ь 5 таких, что р лежит на открытом отрезке аЬ.
Множество Е крайних точек 5 представляет собой наименьшее подмножество 5, обладающее тем свойством, что conv(?) = = conv(S), и Е в точности совпадает с множеством вершин conv(S).
Отсюда следует, что для того, чтобы найти выпуклую оболочку конечного множества точек, требуется выполнить следующие два шага:
126
Гл. 3. Выпуклые оболочки: основные алгоритмы
1. Определить крайние точки. (Это задача В02 в двумерном случае.)
2. Упорядочить эти точки так, чтобы они образовывали выпуклый многоугольник.
Необходима теорема, которая позволит нам проверять, является ли некоторая точка крайней.
Теорема 3.4. Точка р не является крайней плоского выпуклого множества S только тогда, когда она лежит в некотором треугольнике, вершинами которого являются точки из S, но сама она не является вершиной этого треугольника1) (рис. 3.3).
Рис. 3.3. Точка р не является крайней, так как она находится внутри треугольника (Р\Р2Рз).
Эта теорема дает идею для алгоритма удаления точек, не являющихся крайними. Имеется 0(N3) треугольников, определяемых N точками множества 5. Проверка принадлежности точки заданному треугольнику может быть выполнена за некоторое постоянное число операций, так что за время 0(N3) можно определить, является ли конкретная точка крайней. Повторение этой процедуры для всех N точек множества S потребует времени О (Л/4). Хотя наш алгоритм является чрезвычайно неэффективным, он очень прост в идейном плане и показывает, что крайние точки могут быть определены за конечное число шагов.
Мы затратили время 0(NA) только на определение крайних точек, которые должны быть как-то упорядочены, чтобы образовать выпуклую оболочку. Смысл этого порядка раскрывается следующими теоремами.
') Это непосредственно следует из доказательств теорем 10 и 11 в книге [Hadwiger, Debrunner (1964)]. Теорему 3.4 можно обобщить на случай d-мерного пространства, заменив «треугольник» на «симплекс с d + 1 вершинами». Заметим, что треугольник может вырождаться в отрезок, когда его вершины становятся коллинеарными.
