Алгоритмы и структуры данных 14. Триангуляция Делоне: вероятностный алгоритм
Channel: Лекторий ФПМИ
Date: 10/12/2021

00:00:00 - О московском четвертьфинале ICPC (и бонусах к зачёту и экзамену)
00:01:37 - Напоминание определений
00:05:12 - Почему граф Делоне является плоским (планарным)?
00:13:10 - Теорема о вершинах и рёбрах графа Делоне
00:21:10 - Первый критерий триангуляции Делоне
00:24:25 - Операция edge flip
00:26:15 - Определение нелегального ребра
00:28:29 - Критерий легальности
00:31:52 - Когда точка лежит внутри круга, описанного вокруг треугольника?
00:34:25 - Какая триангуляция называется легальной?
00:34:51 - Как сделать любую триангуляцию легальной?
00:38:10 - Второй критерий триангуляции Делоне
00:39:56 - Максимизирует ли триангуляция Делоне минимальный угол?
00:43:09 - Как построить триангуляцию Делоне?
00:51:05 - За сколько работает алгоритм построения триангуляции Делоне?
00:53:57 - Как перемешивать сайты в случайном порядке?
01:00:17 - Как легализовать ребро?
01:09:20 - Как решать задачу о локализации?
01:17:16 - Как обрабатывать фиктивные точки?

Дата лекции: 09.12.2021
Лектор: Степанов Илья

Монтаж: Алексей Горбулев