Алгоритмы и структуры данных 14. Триангуляция Делоне: вероятностный алгоритм

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 Лектор: Степанов Илья Монтаж: Алексей Горбулев