# конспект · шаг 7 из 7
Конспект: триангуляция Делоне
Понятия
Триангуляция набора точек - разбиение выпуклой оболочки на треугольники с вершинами в точках набора, к которому нельзя добавить ребро.
Вектор углов - все углы триангуляции по возрастанию; сравнивают лексикографически.
Триангуляция Делоне - все описанные окружности пусты. Нелегальное ребро - противоположная вершина соседнего треугольника внутри окружности. Переворот - замена диагонали четырёхугольника.
Подъём на параболоид - (x, y) → (x, y, x² + y²).
Рандомизированное инкрементное построение - вставка в случайном порядке; обратный анализ - цена шага через вероятность, что последний объект был нужен ответу.
Что унести
СЧЁТ (формула Эйлера)
треугольников 2n − 2 − h, рёбер 3n − 3 − h - у ЛЮБОЙ триангуляции
триангуляций выпуклого n-угольника - число Каталана C(n − 2)
средний угол всегда 60°: сравнивают наименьший
ромб: диагональ AC - высота 20 и угол 27°, BD - 100 и 53°
ПРЕДИКАТ «В ОКРУЖНОСТИ»
| ax−dx ay−dy (ax−dx)²+(ay−dy)² |
| bx−dx by−dy (bx−dx)²+(by−dy)² | > 0 ⇔ d внутри окружности abc
| cx−dx cy−dy (cx−dx)²+(cy−dy)² | (a, b, c против часовой)
= поворот поднятых точек в 3D; целые - точно
координаты до 1000 → значения порядка 10¹⁴, запас до 2⁵³ небольшой
ПЕРЕВОРОТЫ
пока есть нелегальное ребро uv (треугольники uvx и vuw):
заменить на uwx и wvx
кончается: вектор углов строго растёт; O(n²) переворотов
итог - Делоне: наибольший наименьший угол
20 точек: 149 плохих пар → 0 за 24 переворота, sin угла 0,012 → 0,057
одного прохода мало: переворот портит соседние рёбра
нужен угол не меньше заданного - добавлять точки (Рупперт)
ДВОЙСТВЕННОСТЬ И ВЛОЖЕНИЯ
ребро Делоне ↔ общая граница ячеек Вороного
треугольник Делоне ↔ вершина Вороного (центр окружности)
Делоне = проекция нижней оболочки поднятых точек (scipy - через Qhull)
разные расстояния: ближайшие ⊆ остовное дерево ⊆ Габриель ⊆ Делоне
остовное дерево: Крускал по 3n − 3 − h рёбрам, 49 вместо 190
СЛУЧАЙНЫЙ ПОРЯДОК
наименьшая окружность (Вельцль 1991): O(n) в ожидании,
опорных точек <= 3 → дорогой шаг с вероятностью <= 3/i
40 точек: 203 проверки против 3942 «от центра наружу»
среднее: 5,3-5,8 проверки на точку; дорогих шагов 7-8 при оценке 9-11
Делоне (Гибас, Кнут, Шарир 1992): O(n log n) в ожидании,
средняя степень < 6 → < 3 переворотов на вставку
линейное программирование на плоскости (Зайдель 1991): O(n)
на практике - случайные пачки, упорядоченные по кривой Гильберта (BRIO)
Ловушки джокера
Перебрать триангуляции, чтобы найти лучшую. Их экспоненциально много, а Делоне строится за
n · log n.
Предикат через центр и радиус во float. Около четырёх точек на окружности перевороты ходят по кругу.
Один проход переворотов. Каскады остаются нелегальными.
Перевернуть при < 0 вместо > 0. Портятся легальные рёбра, и процесс зацикливается.
Ждать от Делоне хороших углов на любых точках. Она даёт лучший наименьший угол из возможных, а не большой.
Подать вход как пришёл. Отсортированные данные - худший порядок для инкрементных алгоритмов.
Остовное дерево по порогу расстояния. Либо теряет рёбра, либо оставляет почти все пары.
Проверь себя
Почему у всех триангуляций одно число треугольников? Чем Делоне лучше других и как это проверить
местно? Почему перевороты кончаются и кончаются именно Делоне? Как Делоне связана с Вороным и с
параболоидом? Почему остовное дерево лежит в Делоне? Что считает обратный анализ и откуда берётся 3/i?
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий