Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Доказательство. Если точка р, не лежит на границе выпуклой оболочки множества S, то, согласно теореме 3.4, она является внутренней точкой некоторого треугольника р\р2Рз- Рас-
254
Гл. 5. Близость: основные алгоритмы
смотрим окружности С12, С!3 и С23, определяемые точкой pi и тремя парами точек {pi,p2}, {рьРз} и {р2, р3} соответственно (рис. 5.20). Каждая из этих окружностей имеет конечный радиус. Обозначим через А\2 внешнюю дугу окружности С\2, т. е. дугу окружности между точками pi и р2, не содержащую точку Pi. Можно непосредственно показать, что любая точка А\2 ближе к р\ или к р2, чем к pi (аналогичное утверждение имеет место и для С13 и С23). Пусть С — окружность, охватывающая окружности С\2, С\Ъ и С23. Утверждается, что любая точка х, лежащая вне С, ближе к одной из точек р\, р2 или рз, чем к pi. Действительно, рассмотрим отрезок xpi. По теореме о жордановой кривой отрезок xpi пересекает одну из сторон треугольника pip2p3, например рхр2. Значит, он также пересекает и А12 в некоторой точке \и. Но и ближе к одной из точек pi или р2, чем к Рис. 5.20. К доказательству теоре- р<, что и подтверждает сде-мы 5.10. данное утверждение. Так как
точка х ближе к рь р2 или р3, чем к pi, то V(i) целиком содержится внутри С и, следовательно, является ограниченным.
Обратно, предположим, что многоугольник V(i) ограничен, и пусть ей е2, eft (k ^ 3) — последовательность ребер, образующих его границу. Каждое ребро eh (h = 1, ..., k) принадлежит прямой, перпендикулярной отрезку ргр?, p'h^S и делящей его пополам. Отсюда сразу следует, что pt- является внутренней точкой многоугольника р[р'2 ... p'k, т. е. р,- не лежит на границе выпуклой оболочки множества S.
Так как лишь неограниченные многоугольники могут иметь в качестве ребер лучи, то лучи диаграммы Вороного соответствуют парам смежных точек множества S, лежащих на границе выпуклой оболочки.
Рассмотрим теперь граф, двойственный диаграмме Вороного, т. е. граф, уложенный на плоскости и получаемый в результате соединения отрезками каждой пары точек множества S, многоугольники Вороного которых имеют общее ребро. В результате получается граф с вершинами в исходных N точках (рис. 5.21).
5.5. Решение задач о близости методом локусов
255
На первый взгляд граф, двойственный диаграмме Вороного, может показаться довольно необычным, так как ребро диаграммы может даже не пересекаться с двойственным ему ребром (рассмотрите, например, ребра, соединяющие последовательные вершины выпуклой оболочки). Важность двойственного графа во многом обусловлена следующей теоремой Делоне [Delaunay (1934)]:
Рис. 5.21. Прямолинейный граф, двойственный диаграмме Вороного.
Теорема 5.11. Граф, двойственный диаграмме Вороного, является триангуляцией множества S1). sbaM&W-
(Отсюда следует, что диаграмма Вороного может быть использована для решения задачи триангуляции Б.4, но эта теорема имеет значительно более важные следствия.)
Доказательство. Чтобы доказать, что граф, двойственный диаграмме Вороного, является триангуляцией, необходимо показать, что выпуклая оболочка множества S разбивается на треугольники, определяемые точками множества 5. Для этого будет показано, что можно выделить множество треугольников 3~ — {T(v): v — вершина диаграммы Вороного} так, что никакие два из них не пересекаются и каждая точка внутри conv(S) принадлежит одному из этих треугольников (и, следовательно, в точности одному такому треугольнику).
Соответствующие треугольники строятся следующим образом. Пусть и —вершина диаграммы Вороного, принадлежащая одновременно многоугольникам V{1), V(2) и У(3) (см. теорему 5.7). Т (v) — это треугольник с вершинами в точках ри р2
') В такой простой формулировке эта теорема оказывается неверной, если имеется подмножество, содержащее четыре или более точек, лежащих на одной окружности. Однако в этом случае возникающие изменения в триангуляции очевидны.
256
Гл. 5. Близость: основные алгоритмы
и р3. Утверждается, что если Т(и) имеет непустое пересечение с внутренностью conv(S), то треугольник Т (v) невырожденный (т. е. точки pi, р2 и рз не лежат на одной прямой). Действительно, предположим обратное, т. е. что точки рь р2 и ръ лежат на одной прямой. Тогда все три отрезка р1р2, Р1Р3 и р2рз принадлежат одной и той же прямой /, а перпендикулярные этим отрезкам прямые, делящие их пополам, являются параллельными. Так как вершина v является точкой пересечения этих прямых, то о —бесконечно удаленная точка. Отсюда следует, что многоугольники V(l), V(2) и 1/(3) являются неограничен-
окружность C(vi) является описанной вокруг треугольника T(vi)). Если окружности C(v\) и C(v2) не пересекаются, то не пересекаются и треугольники T(vi) и T(v2). Поэтому предположим, что C(vi) и C(v2) имеют общие внутренние точки. Отметим, что в силу теоремы 5.8 ни одна из окружностей не может целиком содержать другую, поэтому окружности C(v\) и C(v2) пересекаются в двух точках qi и q2, которые определяют прямую / (рис. 5.22), отделяющую точки v\ и v2 друг от друга. Покажем, что / также отделяет треугольник T(v\) от треугольника T(v2). Предположим обратное: в полуплоскости, определяемой / и содержащей вершину v2, имеются точки треугольника T(v\) (т. е. в области, заштрихованной на рис. 5.22, так как T{v\)<^ C(v\)). Отсюда следует, что в заштрихованную область, а следовательно, и в C(v2) попадает вершина треугольника T(vi), что противоречит теореме 5.8. Таким образом, T(v\) и T(v2) не имеют общих внутренних точек.
