Об одном интересном свойстве триангуляции Делоне

в 10:45, , рубрики: Алгоритмы, диаграмма Вороного, доказательство, математика, триангуляция Делоне
Триангуляция Делоне.

Триангуляция Делоне.

В процессе решения некоторой задачи, я наткнулся на одно интересное свойство триангуляции Делоне, которое мне не удалось загуглить, как и его применение к решению разных задач. Я уверен, что не являюсь его первооткрывателем, но оно, по крайней мере, не является широко известным. Поэтому я решил написать о нем статью.

Свойство: Если какой-то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что каждый из отрезков в нем не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь - зеленым цветом.

Дальше в статье я приведу пример его использования в задачах, а также формальное его доказательство.

Если вам известно более красивое доказательство этого свойства, или вы его где-то видели - поделитесь, пожалуйста, в комментариях. Также буду благодарен, если вы поделитесь другими решениями для приведенных в статье задач или аналогичными задачами.

Введение

Для начала, напомню, что такое триангуляция Делоне и как она связана с диаграммой Вороного. Эту секцию можно пропустить, если вы достаточно знакомы хотя бы со страницей в википедии.

Триангуляция Делоне - это триангуляция для заданного множества точек S на плоскости, при которой для любого треугольника все точки из S за исключением точек, являющихся его вершинами, лежат вне окружности, описанной вокруг треугольника (или по крайней мере не лежат внутри этой окружности).

Если никакие 4 или более точки множества S не лежат на одной окружности, внутри которой нет другой точки из S - то триангуляция уникальна. В противном случае эти 4 или более точки образуют в триангуляции выпуклый многоугольник, который может быть триангулирован произвольно. Но за пределами этих точек - триангуляция по прежнему уникальна.

Важное свойство триангуляции - в ней O(n) ребер. Это можно доказать, например, через формулу Эйлера для планарных графов: n+t-e=1(1, а не 2, потому что есть еще внешняя область), 3t < 2e, ведь 3t подсчитает каждое внутреннее ребро 2 раза, а каждое внешнее по одному разу. Отсюда получаетсяe<3(n-1).

Триангуляция тесно связана с диаграммой Вороного для множества S - это такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.

Триангуляция Делоне и диаграмма Вороного двойственные структуры: каждая область или "ячейка" диаграммы соответствует вершине триангуляции Делоне. Если две ячейки соседствуют по стороне, то в триангуляции обязательно есть отрезок между двумя соответствующими точками. Если же в триангуляции есть отрезок - то две ячейки точно соседствуют, хотя бы по вершине. Эти два утверждения немного не симметричны, потому что когда более 3 ячеек пересекаются по одной и той же вершине, то получаятся многоугольки, упомянутый выше, который может быть триангулирован произвольно. Поэтому не факт что между любыми двумя ячеками, соседствующим по вершине обязательно есть отрезок в триангуляции. Вот пример из википедии:

Красным показана диаграмма Вороного. Черным - триангуляция Делоне.

Красным показана диаграмма Вороного. Черным - триангуляция Делоне.

Задачи

Тут я приведу несколько задач, которые решаются через триангуляцию Делоне благодаря найденому свойству. Все эти решения за O(n log n), ведь триангуляцию, как и диаграмму, можно построить за O(n log n), а дальше что-то остается делать лишь с O(n) отрезками. Наивное же решение обычно O(n^2) - по количеству всех возможных отрезков, или даже хуже.

  1. Найти две ближайшие точки во множестве точек.

    Решение
    : построим триангуляцию Делоне и найдем минимальный отрезок в ней, он и будет ответом.

    Примечание: Для этой задачи есть и другое широко известное решение методом "разделяй и властвуй". Но эта задача хорошо демонстрирует принцип применения найденного свойстваа, поэтому я ее оставил.

    Доказательство: Рассмотрим две ближайшие точки во множестве. Если отрезок между ними попал в триангуляцию, то уже найден этот оптимальный ответ. В противном случае, по свойству, в триангуляции есть путь из отрезков не короче этого отрезка, но раз он кратчайший по определению, то все эти отрезки в пути той же длины. Значит, алгоритм найдет какой-то другой отрезок с такой же оптимальной длиной.

  2. Найти расстояние между двумя множествами точек.

    Решение: Через сортировку или хеш-таблицу проверим, а не совпадают ли 2 какие-то точки из разных множеств. В противном случае построим триангуляцию Делоне для объедененного множества точек. Найдем минимальный отрезок в триангуляции, у которого концы из разных множеств, это и будет ответ.

    Доказательство: Аналогично предыдущей задаче. Рассмотрим две ближайшие точки из множеств. Если отрезок между ними оказался в триангуляции - алгоритм найдет этот правильный ответ. В противном случае будет путь из отрезков такой же длины или короче. Этот путь начинается в одном множестве, а заканчивается в другом, значит какой-то из отрезков в нем имеет концы вы разных множествах. Этот отрезок будет не длинее оптимального и алгоритм его рассмотрит, а значит - найдет правильный ответ.

  3. Найти минимальное остовное дерево на множестве точек.

    Решение: Построим триангуляцию Делоне. Найдем минимальное остовное дерево в этом графе.

    Примечение: Факт, что триангуляция Делоне содержит минимальное остовное дерево, упомянут на просторах инернета, но его доказательства я не нашел, поэтому привожу и эту задачу.

    Доказательство: Сначала допустим, что мы ищем остовное дерево алгоритмом Краскала в полном графе с n(n-1)/2 ребрами. Алгоритм очевидно работает. Теперь допустим, что при сортировке ребер одинаковой длины мы сначала берем ребра из триангуляции, а потом те - что туда не вошли. Алгоритм все еще работает. А теперь покажем, что при рассмотрении ребер не в триангуляции, алгоритм всегда их пропустит, потому что два конца уже будут в одной компоненте связности. И правда, ведь по свойству получается, что есть путь между концами, и все ребра там уже будут рассмотрены - ведь они или короче, или той же длины, но из триангуляции, а поэтому идут раньше в сортировке. А значит, два конца ребра уже принадлежат одной компоненте. Поэтому ребра не из триангуляции можно просто исключить из рассмотрения и результат алгоритм не поменяется. Вот мы и построили минимальное остовное дерево во всем графе, рассмотрев только ребра из триангуляции. А теперь можно забыть о конкретном алгоритме. Не важно как мы ищем минимальное остовное дерево, мы же уже доказали, что оно там есть.

  4. Есть N радио башен на плоскости. Две башни могут обмениваться сообщениями, если они на расстоянии не более R. Опеределить, связна ли сеть из всех башен.

    Решение: Построим триангуляцию Делоне, оставим из нее только те ребра, которые не длинее R. Проверим, что граф связен.

    Доказательство: Рассмтрим какое-то ребро полного графа AB, длиной не более R. Если оно вошло в триангуляцию, то два конца будут в одной и той же компоненте. Если оно не вошло, то в триангуляцию войдет путь из ребер не длинее |AB|, а поскольку |AB|не длиннее R, то все эти ребра также будут не длинее R. Получается, что A и B все-равно будут в одной компоненте связности. Поэтому граф из ребер только в триангуляции имеет те же самые компоненты связности, что и полный граф.

  5. Есть N радио башен на плоскости. Две башни могут обмениваться сообщениями, если они на расстоянии не более R. Найти минимальное значение R, при котором связна сеть из всех башен.

    Решение: Построим триангуляцию Делоне. Будем добавлять ребра оттуда в порядке возрастания длины, пока граф не станет связным. Длина последнего добавленного ребра - ответ.

    Доказательство: На самом деле, эта задача аналогична 3-ей задаче про остовное дерево. Ведь минимальное остовное дерево минимизирует не только сумму длин ребер, но и максимальное ребро в дереве. Это очевидно хотя бы по алгоритму Краскала.

Доказательство свойства

Допустим отрезок AB не включен в триангуляцию. Рассмотрим диаграмму Вороного. Отрезок пересекает какие-то ячейки. Обозначим центры этих ячеек как P_1,P_2,...P_k(в порядке пересечения отрезка от A к B).

Очевидно, P_1=A, P_k=B

Заметим, что отрезки P_iP_{i+1}включены в триангуляцию, потому что это центры соседних по стороне ячеек Вороного.

Допустим сначала, что отрезок AB не пересекает ни одну вершину диаграммы Вороного (точку, где соседствуют 3 и более ячейки). Обозначим точки, в которых AB пересекает границу между P_i и P_{i+1} как T_i.

Поскольку T_i лежит на границе ячейки для точки P_i, то |P_i T_i| le |A T_i|, ведь эта ячейка - это геометрическое место точек, которые ближе к P_i чем к любой другой точке из S, в том числе и к A. При чем это неравенство в силе, даже для i=1, ведь если P_i=A, то P_i T_iи AT_i - это один и тот же отрезок.

Аналогично для ячейки P_{i+1} получаем, что |P_{i+1}T_i| le |BT_i|.

По неравенству треугольника получаем |P_iP_{i+1}| le |P_iTi|+|P_{i+1}T_i|
Применяем два полученных раньше неравенства: |P_iP_{i+1}| le |AT_i| + |BT_i|
Заметим, что тут справа получилось два куска, составляющих отрезок AB, и вот мы получили искомое неравенство: |P_iP_{i+1}| le |AB|

Осталось только разобраться со случаем, когда отрезок проходит через вершину в диаграмме Вороного. Тут можно считать, что отрезок проходит подряд через все ячейки, которых он касается в порядке обхода против часовой стрелки. Вот поясняющая картинка:

Об одном интересном свойстве триангуляции Делоне - 26

Мы получим новый список P_i, где каждые 2 соседние точки будут центрами соседних по стороне ячеек, а значит между ними будет отрезок в триангуляции. В качестве точки T_i будем брать все ту же вершину диаграммы, через которую AB проходит. Во всех выкладках выше про длины отрезков нам важно было лишь что T_i лежит на границе ячейки: хоть на стороне, хоть в вершине.

Вот мы и доказали, что в триангуляции содержится путь из отрезков, каждый из которых не превосходит |AB|. ЧТД.

Возможно, стоило бы более формально доказать, что отрезок AB пересекает конечное множество ячеек, каждую по одному разу в однозначно определимом порядке, но это все следует из выпуклости ячеек диаграммы Вороного и показалось мне излишним формализмом.

Другой спорный момент, а что будет, если отрезок AB проходит через какой-то центр ячейки диаграмы Вороного. Это ничего не портит, просто вот этот вот центр будет какой-то очередной P_iи путь из отрезков в триангуляции просто где-то коснется отрезка AB в этой вершине.

Еще возможно доказательство исключительно через триангуляцию Делоне, но там, кажется, получается более муторное доказательство с кучей геометрических выкладок. Я его даже до конца доводить не стал.

Автор: Илья

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js