Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Каждая из N исходных точек множества принадлежит в точности одному многоугольнику Вороного. Поэтому, если (х,y)^V(i), то pi является ближайшим соседом точки (х,у). Диаграмма Вороного содержит всю информацию о близости точек соответствующего множества.
5.5.1. Свойства диаграммы Вороного
Здесь будет приведен ряд важных свойств диаграммы Вороного. Хотя диаграмму Вороного можно определить для пространства любой размерности, последующее обсуждение будет вестись для двумерного случая. На то имеются две причины: во-первых, стремление обеспечить связь проводимых рассуждений с интуицией; во-вторых, желание сосредоточить обсуждение лишь на изученных ситуациях, для которых разработаны эффективные алгоритмы решения возникающих задач.
В этом разделе мы будем считать справедливым следующее предположение:
Предположение А. Никакие четыре точки исходного множества S не лежат на одной окружности.
Если отказаться от этого предположения, то в формулировки теорем и их доказательства потребуется внести несущественные, но довольно длинные уточнения.
Для начала заметим, что каждое ребро диаграммы Вороного является отрезком прямой, перпендикулярной отрезку, соединяющему некоторую пару точек множества S, и делящей этот отрезок пополам. Таким образом, ребро принадлежит в точности двум многоугольникам. Имеет место следующая теорема:
') Такие многоугольники впервые были глубоко изучены русским математиком Г. Вороным (1868—1908), использовавшим их в работе по квадратичным формам [Voronoi (1908)]. Иногда их также называют многоугольниками (ячейками) Дирихле, многоугольниками Тиссена, ячейками Вигнера — Зейтца. Хоуи предложил более образный (и более подходящий) термин «многоугольники близости».
Гл. 5. Близость: основные алгоритмы
Теорема 5.7. Каждая вершина диаграммы Вороного является точкой пересечения в точности трех ребер диаграммы.
Доказательство. Предположим, что вершина v является точкой пересечения некоторого множества ребер е\, е2, ¦ ¦ ¦, ей (k^2), перечисленных в порядке обхода вокруг вершины по часовой стрелке (рис. 5.17). Ребро е,- является общим для многоугольников V(i—1) и V(i), где i = 2, k, а ребро в\ является общим для V(k) и V(l). Заметим, что так как v принадлежит ребру е-i, то она одинаково удалена от точек p,_i и р^ С другой стороны, аналогичным образом получаем, что
Рис. 5.17. Вершина диаграммы Во- Рис. 5.18. Окружность C(v) не со-роного с инцидентными ей ребрами. держит ни одной точки множества S.
она равноудалена от точек р,- и p1+i и т. д. Таким образом, вершина v равноудалена от точек pi, р2, ..., Pk- Но это значит, что точки pi, р2, .... pk лежат на одной окружности, и тем самым в случае k ^ 4 нарушается принятое предположение А. Следовательно, k ^ 3. Предположим теперь, что k — 2. В этом случае оба ребра е\ и е2 принадлежат многоугольникам V(2) и У(1), поскольку оба они принадлежат перпендикуляру, делящему пополам отрезок pip2. А так как они не пересекаются в v, то вновь получаем противоречие.
Теорема 5.7 эквивалентна следующему утверждению: вершины диаграммы Вороного являются центрами окружностей, каждая из которых определяется тремя точками исходного множества, а сама диаграмма Вороного является регулярной1) со степенью вершин, равной трем. Обозначим через C(v) упомянутую выше окружность, соответствующую вершине v. Эти окружности обладают следующим интересным свойством:
') В том смысле, как это обычно понимается в теории графов; граф является регулярным, если все вершины имеют одну и ту же степень.
5.5. Решение задач о близости методом локусов
253
Теорема 5.8. Для каждой вершины v диаграммы Вороного множества S окружность C(v) не содержит никаких других точек множества S.
Доказательство. Докажем теорему методом «от противного». Пусть pi, Р2 и рз — три точки множества S, определяющие окружность C(v) (рис. 5.18). Если окружность C(v) содержит еще некоторую точку множества S, например р4, то вершина v находится ближе к р4) чем к любой из точек рь р2 или р3, и в этом случае в соответствии с определением диаграммы Вороного вершина v должна находиться в V(4), а не в каком-либо из многоугольников V(l), V(2) или V(3). Но это противоречит тому, что вершина и принадлежит одновременно V(l), V(2) и V(3).
Теорема 5.9. Каждый ближайший сосед точки pi в S определяет ребро в многоугольнике Вороного V(i).
Доказательство. Пусть р;- является ближайшим соседом р,, а и — середина соединяющего их отрезка. Предположим, что v не лежит на границе V(i). Тогда отрезок р,у пересекает некоторое ребро многоугольника V(i), например равноудаленное от
Рис. 5.19. Каждый ближайший сосед точки р,- определяет ребро многоуголь-
р, и pk, в некоторой точке и (рис. 5.19). Тогда длина(р,и)< < длина (piv) и _поэтому длина (р,р*) ^ 2 длина (р,и) < 2 длина (piv) = длина (pip,), откуда следует, что pk ближе к р,, чем Pi, что противоречит условию теоремы.
Теорема 5.10. Многоугольник V(i) является неограниченным тогда и только тогда, когда точка pi лежит на границе выпуклой оболочки множества S.
