Прямая с наибольшим кол-вом пересечений с триангуляцией
Дан выпуклый многоугольник с триангуляцией и надо найти такую прямую внутри многоугольника, чтобы она имела максимум пересечений с диагоналями его триангуляции. Решать задачу можно перебором всех возможных прямых, а можно использовать как-то триангуляцию и тогда сложность алгоритма должна получится приблизительно линейной. Есть какие-то варианты как можно это сделать? Суть найти максимум пересечений, а то что может при этом получится мн-во решений в виде различных прямых не так важно.
Ответы (1 шт):
Триангуляция может быть задана диагоналями (парами индексов вершин) или треугольниками (тройками индексов вершин). Если даны диагонали, за линейное время можно восстановить треугольники.
Если эта часть вызывает трудности, напишите комментарий, дополню.
Определим двойственный граф триангуляции. Вершины графа - треугольники триангуляции. Две вершины связаны ребром если соответствующие треугольники имеют общую диагональ в триангуляции. Двойственный граф является двоичным деревом.
Наблюдение: любой прямой которая пересекает тринагуляцию соответствует путь на двойственом дереве. Проверяется непосредственно: в путь попадают все пересечённые треугольники. Если точка двигается по прямой, то она перечисляет треугольники. Когда точка пересекает диагональ, она из одного треугольника переходит в его соседа в двойственном дереве.
Путь всегда начинается и заканчивается в листьях дерева.
Обратное утверждение: любому пути из листа в лист соответствует некоторая прямая пересекающая все треугольники пути и не пересекающая другие треугольники.
Обратное утверждение проверяется непосредственно. Из данного пути возьмём треугольники-листья. В обоих выберем точки внутри. Через точки проведём прямую. Эта прямая отобразится в путь на двойственном графе между данными листьями. Такой путь единственнен, значит мы предьявили прямую которая соответствует пути.
Вернёмся к исходной задаче. Для данной прямой количество пересечённых диагоналей на единицу больше числа треугольников в соответствующем пути. Самый длинный путь соответствует самому большому количеству пересечений. Нужно найти самый длинный путь внутри дерева. Другими словам нам нужен диаметр дерева.
Поиск диаметра дерева хорошо известен. Задача решается за линейное время.
Итого:
- по триангуляции за линейное время строим дерево;
- отыскиваем диаметр дерева за линейное время;
- длину диаметра переводим в количество пересечений.
P.S. По времени ваш вопрос хорошо совпадает с курсовой моего студента, которому я обещал что задача интересная и забавная. Передавайте привет. :)
P.P.S. Задача забавная потому что для решения не нужны координаты вершин многоугольника. Достаточно его выпуклости. В итоге задача становится чисто комбинаторной: программа работает с индексами концов диагоналей.