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

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

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

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

Введение

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

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

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

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

Триангуляция тесно связана с диаграммой Вороного для множества 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 не включен в триангуляцию. Рассмотрим диаграмму Вороного. Отрезок пересекает какие-то ячейки. Обозначим центры этих ячеек как (в порядке пересечения отрезка от A к B).

Очевидно, ,

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

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

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

Аналогично для ячейки получаем, что .

По неравенству треугольника получаем
Применяем два полученных раньше неравенства:
Заметим, что тут справа получилось два куска, составляющих отрезок AB, и вот мы получили искомое неравенство:

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

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

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

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

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

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