Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
В пространстве Еъ особую роль играет единичная сфера (сфера единичного радиуса с центром в начале координат), так как точки этой сферы остаются неподвижными при инверсии. На рис. 6.11 показан пример преобразования инверсии на плоскости. На этом рисунке прямая h (i = 1, 2, 3) и окружность Ct при инверсии преобразуются друг в друга.
6.3.1.2. Структура диаграмм Вороного высших порядков
Теперь мы готовы к обсуждению основного вопроса. Пусть 5 — множество из N точек на плоскости. Поместим эту плоскость в пространство Еъ с координатами х, у и г, совместив ее с плоскостью z = 1 (заметим, однако, что можно было выбрать любую другую плоскость). Построим образ этой плоско-
Гл. 6. Близость: варианты и обобщения
сти при инверсии, т. е. сферу С радиусом 1/2 с центром в точке (0,0,1/2). (См. рис. 6.12, отражающий аналогичную ситуацию в пространстве меньшей размерности.) Отобразим каждую точку множества S в точку на С путем проектирования вдоль прямой, проходящей через начало координат в Е31). В результате этого на сфере С получим множество S' из N точек.
Рассмотрим теперь плоскость л, определяемую тремя точками р\, p'j и р\ множества S' (эти точки являются образами точек pi, pj и pi множества 5 при преобразовании инверсии).
сфера
Рис. 6.12. Преобразование инверсии отображает множество точек, лежащих в плоскости z = 1, на сферу С.
(См. рис. 6.12.) Эта плоскость определяет на сфере С сегмент, не содержащий начало координат. Обозначим через S'(n)^S' подмножество точек множества S', попавших внутрь этого сегмента сферы. Заметим, что S'(n) содержит точки, лежащие внутри полупространства Я (л), определяемого плоскостью л и не содержащего начала координат. Рассмотрим образ плоскости л при инверсии, обозначив его С (л). Как мы уже знаем, С (л) — это сфера, проходящая через начало координат и точки Pi, р,- и pi (сфера однозначно определяется этими четырьмя точками). Так как внутренние точки полупространства Я (л) отображаются внутрь сферы С (л), то образы точек множества S'(n) при инверсии попадают внутрь С(л). В частности, они попадают внутрь окружности С (pi, ph pt), проходящей через точки pi, pj и pi, так как эта окружность является пересечением сферы С (л) с плоскостью z = 1. Обозначим буквой v центр окружности С (pi, ph pi), a R cz S — подмножество точек мно-
') Такая проекция называется стереографической.
6.3. Обобщения диаграммы
301
жества S, лежащих внутри C{p„phpt) (очевидно, что R является образом S'(n)). Утверждается, что v является вершиной в некоторой диаграмме Вороного высшего порядка. Действительно, положим \R\ = k и предположим на время, что 0 <i k <. N — 13. Очевидно, что R содержит точки, находящиеся от v на меньшем расстоянии, чем любая из точек {pi,Pi,pi}-Точка v буде1 вершиной диаграммы Вороного порядка (&+ 1), являясь общей точкой многоугольников V(R\j {pi}), V(R[} U{p/}) и V(R\j {pi}), и вершиной диаграммы порядка (k-\-2), являясь обшей точкой многоугольников V{R [} {pi, р/}), V(R{] \J{p',pii) и V(RU {р<,Р/}). Если R = 0 и, значит, k = 0, то v являьтся вершиной лишь Vori(S), а если |/?| = N — 3, то v является вершиной лишь Vor>_i(S). Теперь обратим внимание на
каждая такая плоскость определяет вершину диаграммы Вороного (большинство из них являются вершинами двух диаграмм Вороного высших порядков). Так как каждая диаграмма Вороного является планарным графом и каждая вершина диаграммы имеет степень не менее трех (на самом деле в точности три, за исключением вырожденных вершин), то в каждой диаграмме Vovk{S), k = 1, N—1, число многоугольников пропорционально числу вершин. Объединяя эти факты, получаем следующий интересный результат [Brown (1979а), (1979b)].
Теорема 6.8. Число многоугольников Вороного в диаграммах всех порядков равно О (N3).
Чтобы добиться более глубокого понимания структуры диаграмм Вороного, воспользуемся подходом, аналогичным подходу, недавно предложенному Эдельсбруннером и Зейделем [Edelsbrunner, Seidel (1986)]. Рассмотрим стереографическую проекцию, представляющую сужение инверсии в пространстве ?3 на плоскость г = 1 (или, что эквивалентно, на сферу С, являющуюся образом этой плоскости). Выпишем явно уравнение сферы С:
Предположим теперь, что мы применяем к Е3 некоторое подходящее проективное преобразование ф. Обозначим через g, ц и ? координаты в преобразованном пространстве. В частности, нас интересует преобразование, отображающее плоскость г = 0 в бесконечно удаленную плоскость. Мы осуществим это преобразование следующим образом: сначала введем в Е3 однородные координаты х\, х2, х3 и х4 (см. разд. 1.3.2, где обсуждается связь между однородными и неоднородными координатами), за-
то, что плоскость я может
(6.1)
302
Гл. 6. Близость: варианты и обобщения
тем рассмотрим их как координаты в ?4 и, наконец, применим к Ei преобразование поворота, выражаемое следующим соотношением (здесь lu %2, h и g4 однородные координаты в преобразованном пространстве):
г 1 о о о
0 10 0
0 0 0 1
0 0 10
¦ (*,, хъ Хй, Х4)Г.
(6.2)
