Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
V{T) = {p: Va е= ГУда eS-Г, d(p, v)<d(p, ш)}.
То есть V(T) — это множество точек на плоскости, таких что каждая точка из Т ближе к некоторой точке pG V(T), чем
6.3. Обобщения диаграммы
297
любая точка, не принадлежащая Т. Дадим эквивалентное определение:
У(Т) = Г]Н(р„ р,), Pi^T, p,e=S-T,
где H(pi,pj), как обычно, представляет полуплоскость, содержащую pi и определяемую прямой, перпендикулярной отрезку pipi и делящей его пополам. Это определение показывает, что обобщенный многоугольник Вороного по-прежнему является выпуклым. Конечно, может оказаться, что V(T) пусто. В примере на рис. 6.10 отсутствуют точки, для которых их двумя ближайшими соседями являются точки ps и р7. Множество 5, содержащее N точек, имеет 2N подмножеств. Для скольких из них многоугольники Вороного непустые? Если соответствующее число невелико, то есть надежда организовать поиск k ближайших соседей, не используя для этого чрезмерный объем памяти.
Ощ^елим диаграмму Вороного порядка k, обозначив ее Vorft(5) — как совокупность всех обобщенных многоугольников Вороного /^-элементных подмножеств множества 5. Таким образом '),
Vor* (S) = U V (Т), 7-czS, |7-! = k.
При такой записи обычная диаграмма Вороного это просто Vor^S). Название «диаграмма» для Vor*(S) вполне уместно, так как ее многоугольники разбивают плоскость на части. Если задана диаграмма Vor^(S), то k ближайших соседей некоторой новой точки q можно найти, определив многоугольник, в котором находится q. На рис. 6.10 показана диаграмма Вороного второго порядка, содержащая области, определяющие пары ближайших точек.
Прежде чем приступать к обсуждению вычислительных задач, связанных с построением обобщенных диаграмм Вороного, необходимо изучить их структуру. Этому вопросу посвящен следующий раздел.
6.3.1.1. Элементы инверсной геометрии
Начнем с небольшого отступления в область инверсной геометрии — средства, которое особенно подходит для наших целей.
') Правильнее записать так: Vor^ (S) = [}{V (Г)}, TczS. | Т | = k. - Прим. перев.
Гл. 6. Близость: варианты и обобщения
Определение 6.2. Инверсия в пространстве Ed — это преобразование, переводящее точку, определяемую вектором v, в точку, определяемую вектором v' = v • 1/1 v |2').
Заметим, что инверсия является инволюцией, так как скалярное произведение v и ее образа v' равно единице:
v • v'r = v • vr т-^-р- = 1,
и, значит, v и v' являются образами друг друга при преобразовании инверсии. Рассмотрим одно характерное свойство инверсии, выражаемое следующей теоремой:
Теорема 6.7. Инверсия в пространстве Ed отображает гиперсферы в гиперсферы.
Доказательство. Гиперсфера а с центром в с и радиусом г — это множество точек v, удовлетворяющих уравнению |v — с j2 = г2. Отсюда сразу получаем 2vcr = |v|2 —f-1 с j2 — г2. Теперь рассмотрим величину |v' — с/(|с|2 — г2)\2, где v — образ точки v при инверсии, т. е. v'= l/|v|2-v. Получаем
\v> с р 1 |с|*___2vJ
Г |с|*-г»| - |v|* + (|c|»-r»)« |v|».(|c|*-r») (1 с |» - Г*)" + | у |« | с [» - | у |« ( | с [» - г») - (| с |» - г*)*
- lvl».(lcll_rl)»
- ( | с |» — г*)*'
Так как эта величина является константой (она зависит от констант |с|2 и г), то отсюда следует, что образом гиперсферы а при преобразовании инверсии является гиперсфера с центром в с/(|с|2 — г2) и радиусом л/(|с[2 — г2).
Преобразование инверсии имеет особенность в начале координат пространства Ей. Образом начала координат является бесконечно удаленная гиперплоскость. Следствием этого является тот факт, что при преобразовании инверсии внутренность гиперсферы а отображается на внутренность ее образа г/ тогда и только тогда, когда о (а значит, и а') не содержит внутри себя начало координат. В противном случае внутренность о отображается на внешнюю область а'.
Для нас, в частности, представляет интерес случай, когда гиперсферы проходят через начало координат, являющийся промежуточным между двумя случаями, упомянутыми выше. Гиперсфера, проходящая через начало координат, отображает-
') Между точками и векторами в ЕЛ имеется взаимно однозначное соответствие. Поэтому далее вместо «точка, определяемая вектором v» будем использовать краткую форму «точка v». — Прим. перев.
6.3. Обобщения диаграммы
ся в гиперплоскость, а внутренность гиперсферы отображается на полупространство (определяемое гиперплоскостью-образом), не содержащее начало координат. Иначе говоря, семейство гиперплоскостей в Ей отображается в семейство гиперсфер, проходящих через начало координат.
Для большей наглядности последующее изложение основывается на рассмотрении двумерного и трехмерного случаев. Кроме того, при обсуждении диаграмм Вороного высших порядков на плоскости мы также воспользуемся трехмерным пространством; однако для простоты на рисунках будет изображаться двумерная ситуация. Таким образом, из предыдущего
Рис. 6.11. Пример преобразования инверсии на плоскости для случая прямых и окружностей, проходящих через начало координат.
обсуждения следует, что при инверсии в случае плоскости окружности переходят в окружности, а в трехмерном пространстве сферы отображаются в сферы.
