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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

Задачи

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

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

Решение: построим триангуляцию Делоне и найдем минимальный отрезок в ней, он и будет ответом.
Примечание: Для этой задачи есть и другое широко известное решение методом «разделяй и властвуй». Но эта задача хорошо демонстрирует принцип применения найденного свойстваа, поэтому я ее оставил.
Доказательство: Рассмотрим две ближайшие точки во множестве. Если отрезок между ними попал в триангуляцию, то уже найдет этот оптимальный ответ. В противном случае, по свойству, в триангуляции есть путь из отрезков не короче этого отрезка, но раз он кратчайший по определению, то все эти отрезки в пути той же длины. Значит, алгоритм найдет какой-то другой отрезок с такой же оптимальной длиной.
Найти расстояние между двумя множествами точек.
Решение: Через сортировку или хеш-таблицу проверим, а не совпадают ли 2 какие-то точки из разных множеств. В противном случае построим триангуляцию Делоне для объедененного множества точек. Найдем минимальный отрезок в триангуляции, у которого концы из разных множеств, это и будет ответ.
Доказательство: Аналогично предыдущей задаче. Рассмотрим две ближайшие точки из множеств. Если отрезок между ними оказался в триангуляции — алгоритм найдет этот правильный ответ. В противном случае будет путь из отрезков такой же длины или короче. Этот путь начинается в одном множестве, а заканчивается в другом, значит какой-то из отрезков в нем имеет концы вы разных множествах. Этот отрезок будет не длинее оптимального и алгоритм его рассмотрит, а значит — найдет правильный ответ.
Найти минимальное остовное дерево на множестве точек.
Решение: Построим триангуляцию Делоне. Найдем минимальное остовное дерево в этом графе.
Примечение: Факт, что триангуляция Делоне содержит минимальное остовное дерево, упомянут на просторах инернета, но его доказательства я не нашел, поэтому привожу и эту задачу.
Доказательство: Сначала допустим, что мы ищем остовное дерево алгоритмом Краскала в полном графе с n (n-1)/2 ребрами. Алгоритм очевидно работает. Теперь допустим, что при сортировке ребер одинаковой длины мы сначала берем ребра из триангуляции, а потом те — что туда не вошли. Алгоритм все еще работает. А теперь покажем, что при рассмотрении ребер не в триангуляции, алгоритм всегда их пропустит, потому что два конца уже будут в одной компоненте связности. И правда, ведь по свойству получается, что есть путь между концами, и все ребра там уже будут рассмотрены — ведь они или короче, или той же длины, но из триангуляции, а поэтому идут раньше в сортировке. А значит, два конца ребра уже принадлежат одной компоненте. Поэтому ребра не из триангуляции можно просто исключить из рассмотрения и результат алгоритм не поменяется. Вот мы и построили минимальное остовное дерево во всем графе, рассмотрев только ребра из триангуляции. А теперь можно забыть о конкретном алгоритме. Не важно как мы ищем минимальное остовное дерево, мы же уже доказали, что оно там есть.
Есть N радио башен на плоскости. Две башни могут обмениваться сообщениями, если они на расстоянии не более R. Опеределить, связна ли сеть из всех башен.
Решение: Построим триангуляцию Делоне, оставим из нее только те ребра, которые не длинее R. Проверим, что граф связен.
Доказательство: Рассмтрим какое-то ребро полного графа AB, длиной не более R. Если оно вошло в триангуляцию, то два конца будут в одной и той же компоненте. Если оно не вошло, то в триангуляцию войдет путь из ребер не длинее |AB|, а поскольку |AB|не длиннее R, то все эти ребра также будут не длинее R. Получается, что A и B все-равно будут в одной компоненте связности. Поэтому граф из ребер только в триангуляции имеет те же самые компоненты связности, что и полный граф.
Есть 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|$

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

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

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

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

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

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