Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Следовательно, наименьшую охватывающую окружность можно получить в результате решения варианта Трехмерной задачи линейного программирования. Комбинируя этот результат с аналогом теоремы 7.12 для трех измерений, получаем следующее усиление теоремы 6.14:
Следствие 7.4. Наименьшую окружность, охватывающую N-точечное множество, можно вычислить за оптимальное время Q(N).
Рис. 7.24. Иллюстрация : ния поверхностей z = f{x,y) = <p(x,y)=f(x,y) + (x* + y*).
') Здесь для простоты исключается возможность существования четырех точек из S, лежащих на одной окружности.
364
Гл. 7. Пересечения
Замечание 2. Особенно интересным приложением линейного программирования является задача о линейной разделимости (рассматриваемая здесь в Ed).
Определение 7.2. Говорят, что два точечных множества S\ и S2 в Ed являются линейно разделимыми, если существует такое линейное (d— 1)-мерное многообразие л, что Si и 52 лежат по разные его стороны. (Для двух измерений я— прямая, а для трех — обычная плоскость.)
Покажем теперь, что линейная разделимость является задачей линейного программирования. Пусть даны два множества точек в d-мерном пространстве: S{ = {(x\l).....x{jA:
'==1.....и S2 = {(*</>.....*<>>): / = 15,1+1.....JS.I +
+1S21}, где I Si I + IS21 = N; ищем одну из плоскостей ptfi + ... + pdxd + pd+l = 0, удовлетворяющих условиям:
( Pla\')+... +pjfit) + Pd+l^0 при 1</<|5,|,
I pA() + • • • + pdaf + pd+l > 0 при IS, I + 1 < / < tf.
Очевидно, что эта задача является задачей линейного программирования, и, согласно предыдущим результатам, ее можно решить за время O(N) при двух и трех измерениях.
7.2.6. Ядро плоского многоугольника
В разд. 2.2.1 было показано, что поиск точки в ядре звездного многоугольника является важным шагом при предобработке, необходимой для ответа на соответствующий вопрос о принадлежности. Тогда мы отложили разработку алгоритма построения ядра до тех пор, пока не появятся необходимые для этого средства. Задача ставится следующим образом:
Задача С.1.5 (ЯДРО МНОГОУГОЛЬНИКА). Дан N-вер-шинный (не обязательно простой) многоугольник на плоскости. Надо построить его ядро.
Во-первых, заметим, что ядром является пересечение N полуплоскостей. Действительно, каждое ребро многоугольника Р определяет одну полуплоскость, в которой должно лежать это ядро (рис. 7.25). Такие полуплоскости называются внутренними (или левыми полуплоскостями сообразно с обходом границы ядра против часовой стрелки). Известно [Yaglom, Boltyanskii (1961)], что ядро многоугольника является пере-
7.2. Плоские приложения
365
сечением его левых полуплоскостей. Поэтому непосредственно получаем, что
ЯДРО МНОГОУГОЛЬНИКА ocjv ПЕРЕСЕЧЕНИЕ ПОЛУПЛОСКОСТЕЙ, и, используя результат разд. 7.2.4 (теорему 7.10), имеем
Следствие 7.5. Ядро произвольного N-угольника можно построить за время O(NlogN).
Заметим, однако, что нижняя оценка Q(NlogN), доказанная в теореме 7.10, неприменима к задаче о построении ядра, поскольку ребра простого многоугольника не могут занимать
Допустимая (внутренняя) V///// Запретная полуплоскость, определен- Г^СУ///, полуплоскость ная ребром и; иг\ / ^yyyy^L^
Рис. 7.25. Каждое ребро многоугольника Р определяет допустимую полуплоскость.
произвольных положений, а значит, нет сводимости к задаче о сортировке. Другими словами, нет оснований считать, что необходимо затратить более чем линейное время для построения _ядр_гц_более того, сейчас будет показано, что такой алгоритм существует [Lee, Preparata (1978)].
Входной многоугольник Р представлен последовательностью вершин (у0, vu vN-i), где N ^ 4, a ei — Vi-\Vi при i— 1, 2, ..., JV — 1 есть ребро, связывающее вершины vi-i и у,- [е0 = = v/r-iVo). Для простоты ссылок опишем P циклическим списком чередующихся вершин и ребер voeiv\в2 ... eN-iVN-ieoVo-Предположим также, что граница P ориентирована против часовой стрелки, т. е. внутренность Р лежит слева от каждого из .ребер. Будем говорить, что вершина и,- вогнута, если внутренний угол при vt больше 180°, и выпукла в противном случае; без потери общности предположим, что нет внутренних углов, равных 180°. Если К(Р) (ядро Р) не пусто, то результатом работы также станет последовательность вершин и ребер
Из этого региона вершина ц не видна, поэтому ядро не может располагаться
здесь
К(Р).
366
Гл. 7. Пересечения
Алгоритм просматривает вершины Р по порядку и строит последовательность выпуклых многоугольников К\, К2, ¦¦¦ Кы-\- Каждый из этих многоугольников может быть либо ограниченным, либо нет. Позднее будет показано (лемма 7.1), что Ki является общим пересечением полуплоскостей, лежащих ???53—01- ориентированных ребер ер, ei, е,. Отсюда, оче-
видно,. следует, что Kn-\ = К(Р) и что К\ э К2 э ... э Кг, последнее означает, что существует такое r0 > 1, что /С,- будет неограниченным или ограниченным в зависимости от условия i < г0 или i г0 соответственно.
Если точки wt и wi+1 лежат на прямой, несущей es. — ребро Р, то обозначим через ауге5.ау,Ч1 отрезок этой прямой,
