Алгоритмы и структуры данных 11. Динамическая оболочка. Rotating calipers. Сумма Минковского

Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Дата лекции: 10.11.2022
Лектор: Степанов Илья Даниилович
Монтажер: Голицын Сергей
Оператор: Жулябина Ира

// начало лекции не записалось. приносим свои извинения
00:00:00 — начало; задача с прошлой лекции: найти максимальное скалярное произведение данного вектора на вектор из множества
00:06:17 — как работать с динамической оболочкой
00:09:37 — rotating calipers (поиск диаметра)
00:10:38 — замечание: диаметр достигается на вершинах выпуклой оболочки
00:12:54 — лемма о диаметре
00:17:49 — алгоритм
00:27:24 — лемма для решения проблемы с неучтенными парами
00:32:28 — теорема о представлении conv(s) при условии на выпуклую комбинацию
00:45:22 — задача (сумма Минковского выпуклых многоугольников)
00:47:25 — утверждение: сумма выпуклых многоугольников — выпуклый многоугольник
01:04:58 — алгоритм, корректность
01:18:11 — проверка двух выпуклых многоугольников на пересечение, поиск расстояния между ними

Видео Алгоритмы и структуры данных 11. Динамическая оболочка. Rotating calipers. Сумма Минковского канала Лекторий ФПМИ