Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Наконец, рассмотрим произвольную точку х в conv(S) и предположим, что она не принадлежит ни одному из треугольников T(v), где v — вершина диаграммы Вороного. Отсюда следует, что существует достаточно маленький круг у с центром в х, все точки которого обладают тем же свойством, что и точка х
ными. Согласно теореме 5.10, это значит, что точки pi, р2 и р3 принадлежат границе выпуклой оболочки. Это противоречит предположению, что Т(v) имеет непустое пересечение с внутренностью conv(S). Тем самым утверждение доказано.
Рис. 5.22. Ни одна точка треугольника T(vt) не попадает внутрь заштрихованной области.
Рассмотрим два треугольника T{vi) и T{v2) (v\ ф v2) и соответствующие им окружности C{v\) и C(v2) (заметим, что
5.5. Решение задач о близости методом локусов
257
(рис. 5.23). Пусть q — некоторая точка в Т(v), где у —произвольная вершина диаграммы. В круге у можно выбрать точку у е= V- такую, что прямая /, проходящая через q и у, не проходит ни через одну из точек множества S. Прямая I пересекает треугольники семейства 3" по некоторому множеству замкнутых интервалов. Обозначим через t конечную точку ближайшего к х интервала и будем считать, что / принадлежит ребру pip2 треугольника T(v\), где v\—некоторая вершина диаграммы Воро-
Рг
>ис. 5.23. Каждая точка внутри выпуклой оболочки множества принадлежит екоторому треугольнику.
ого. Пусть рз —третья вершина треугольника T(v\). Рассмотри перпендикуляр /] из v\ к pip2. Начальная часть 1г совпадает ребром, ограничивающим V(l) и У(2). Так как по предположению точка х находится в conv(S), ахи р3 находятся по раз-ые стороны отрезка pip2, то отрезок pip2 не принадлежит гра-ице выпуклой оболочки множества S. Отсюда следует, что ребро, ежатгге"е на 1и не является лучом (по теореме 5.10), а пред-гавляет отрезок, заканчивающийся в некоторой вершине v2. ледовательно, pi и р2 являются вершинами треугольника (v2), и так как Т (vi)f\T (v2) — 0 (как было показано выше), ) vi и v2 лежат по разные стороны от отрезка pip2. Значит, является внутренней точкой T(v\)\JT(v2), и это противоречит необоснованному) предположению, что точки отрезка ty не зинадлежат ни одному треугольнику из (Г. Предыдущая теорема имеет непосредственное следствие:
Следствие 5.2. Диаграмма Вороного множества из N точек геет не более 2N—5 вершин и 3N — 6 ребер.
Доказательство. Каждому ребру графа, двойственного диа-амме Вороного, соответствует единственное ребро диаграммы, зойственный граф является триангуляцией, а значит, планар-
258
Гл. 5. Близость: основные алгоритмы
кым графом с N вершинами. В соответствии с формулой Эйлера он имеет не более 3N — 6 ребер и 2N— 4 граней. Следовательно, диаграмма Вороного имеет не более 3N — 6 ребер. Однако лишь ограниченные грани (их не более 2N — 5) соответствуют вершинам диаграммы Вороного при отображении двойственности.
Используя введенное понятие двойственности, диаграмму Вороного можно также применить для решения задачи ТРИАНГУЛЯЦИЯ (задача Б.4).
Так как диаграмма Вороного является планарным графом, то для ее представления достаточно линейного по числу точек объема памяти. Это позволяет представить информацию о близости в чрезвычайно компактной форме. Любой конкретный многоугольник Вороного может иметь до N—1 ребер, но полное число ребер не превосходит 3N — 6, при этом каждое ребро принадлежит в точности двум многоугольникам. Это значит, что среднее число ребер многоугольника Вороного не превосходит шести.
В двух последующих разделах рассмотренные свойства будут использованы для быстрого построения диаграммы Вороного и рассмотрено ее применение для решения задач о близости точек.
5.5.2. Построение диаграммы Вороного
Хотя мы будем использовать диаграммы Вороного для решения других задач, следует отметить, что в целом ряде приложений конечной целью является именно построение диаграммы Вороного. В археологии многоугольники Вороного используются для нанесения на карту ареала применения орудий труда в древних культурах и для изучения влияния соперничающих центров торговли [Hodder, Orton (1976)]. В экологии возможности организма на выживание зависят от числа соседей, с которыми он должен бороться за пищу и свет. Использование диаграммы Вороного, отражающей картину расселения животных и распределения жизненно важных ресурсов, помогает исследовать эффект перенаселенности [Pielou (1977)]. Совместное влияние электрических и близкодействующих сил, для изучения которых строятся сложные диаграммы Вороного, помогает определять структуру молекул.
Под задачей построения диаграммы Вороного Vor(S) на множестве точек S, для ссылки на которую мы будем использовать название ДИАГРАММА ВОРОНОГО, будем понимать порождение описания диаграммы как планарного графа, уложенного на плоскости. Это описание должно включать следующие элементы (см. разд. 1.2.3.2):
5.5. Решение задач о близости методом локусов
259
1. Координаты вершин диаграммы Вороного.
2. Множество ребер диаграммы, каждое из которых представляется парой вершин диаграммы. Для каждого ребра указываются два других ребра, следующих за ним при обходе против часовой стрелки в каждой его концевой точке (реберный список с двойными связями, см. разд. 1.2.3.2).
