1

Дан выпуклый многоугольник с триангуляцией и надо найти такую прямую внутри многоугольника, чтобы она имела максимум пересечений с диагоналями его триангуляции. Решать задачу можно перебором всех возможных прямых, а можно использовать как-то триангуляцию и тогда сложность алгоритма должна получится приблизительно линейной. Есть какие-то варианты как можно это сделать? Суть найти максимум пересечений, а то что может при этом получится мн-во решений в виде различных прямых не так важно.

1 ответ 1

1

Триангуляция может быть задана диагоналями (парами индексов вершин) или треугольниками (тройками индексов вершин). Если даны диагонали, за линейное время можно восстановить треугольники.

Если эта часть вызывает трудности, напишите комментарий, дополню.

Определим двойственный граф триангуляции. Вершины графа - треугольники триангуляции. Две вершины связаны ребром если соответствующие треугольники имеют общую диагональ в триангуляции. Двойственный граф является двоичным деревом.

Наблюдение: любой прямой которая пересекает тринагуляцию соответствует путь на двойственом дереве. Проверяется непосредственно: в путь попадают все пересечённые треугольники. Если точка двигается по прямой, то она перечисляет треугольники. Когда точка пересекает диагональ, она из одного треугольника переходит в его соседа в двойственном дереве.

Путь всегда начинается и заканчивается в листьях дерева.

Обратное утверждение: любому пути из листа в лист соответствует некоторая прямая пересекающая все треугольники пути и не пересекающая другие треугольники.

Обратное утверждение проверяется непосредственно. Из данного пути возьмём треугольники-листья. В обоих выберем точки внутри. Через точки проведём прямую. Эта прямая отобразится в путь на двойственном графе между данными листьями. Такой путь единственнен, значит мы предьявили прямую которая соответствует пути.

Вернёмся к исходной задаче. Для данной прямой количество пересечённых диагоналей на единицу больше числа треугольников в соответствующем пути. Самый длинный путь соответствует самому большому количеству пересечений. Нужно найти самый длинный путь внутри дерева. Другими словам нам нужен диаметр дерева.

Поиск диаметра дерева хорошо известен. Задача решается за линейное время.

Итого:

  • по триангуляции за линейное время строим дерево;
  • отыскиваем диаметр дерева за линейное время;
  • длину диаметра переводим в количество пересечений.

P.S. По времени ваш вопрос хорошо совпадает с курсовой моего студента, которому я обещал что задача интересная и забавная. Передавайте привет. :)

P.P.S. Задача забавная потому что для решения не нужны координаты вершин многоугольника. Достаточно его выпуклости. В итоге задача становится чисто комбинаторной: программа работает с индексами концов диагоналей.

5
  • Спасибо, что откликнулись, вроде все выглядит не так сложно как казалось. Попробую разобраться) 18 фев 2022 в 14:47
  • Правильно я понимаю, что если взять к примеру квадрат и поделить его на 4 части (4 треугольника) то получится дерево вида: 1->2->3; 1->4->3 (где 1 корень и мы из него можем перейти в два соседних треугольника пересекая диагонали 2,4 после уже из них переходим в последний 3-й треугольник тем самым диаметр такого дерева (если корень 0) будет равен 2 (пересечения)? 18 фев 2022 в 15:52
  • 1
    Квадрат можно разделить на два треугольника. В этой теории нельзя создавать новые вершины, можно только проводить диагонали между существующими вершинами многоугольника. Диагонали не должны пересекаться. 18 фев 2022 в 15:57
  • Кстати, а каким образом у нас получится линейное время если триангуляция задана случайно и для первого треугольника, чтобы найти для него смежные треугольники нужно просмотреть все остальные разве нет? Даже если учесть, что их не может быть больше 2-х все равно в дальнейшем для других треугольников придется делать проверки. 19 фев 2022 в 13:02
  • 1
    Заведите hashmap {диагональ -> [треугольники]}. Этот hashmap вы заполните за линейное время. В каждом списке [треугольники] окажется ровно два треугольника. Это и есть ребра двойственного графа. Можно обойтись без hashmap, с hashmap проще объяснить. 19 фев 2022 в 13:26

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.