Блог пользователя Berzhik

Нужна помощь!
Автор Berzhik, 15 лет назад, По-русски

Помогите пожалуйста решить такую задачу:

Дано n, и координаты n вершин многоугольника (xi,yi).

Нужно найти минимальную триангуляцию этого многоугольника.

Подскажите пожалуйста какая формула при решении этой задачи динамическим программированием?

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А что требуется минимизировать? Если количество, то, насколько мне известно, всегда существует решение с n-2 треугольниками.
→ Ответить
15 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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

UPD. На фоне этого, мой коммент можно не читать.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Решение для выпуклого многоугольника.
Пусть вершины пронумерованы от 1 до N. Пусть L[i][j] - минимальная сумма длин диагоналей по всем триангуляциям многоугольника, образованного вершинами i, i+1, ..., j. Тогда ответ на задачу это L[1][N]. Как считать L[i][j]? Рассмотрим отрезок соединяющий вершины i и j. Он должен входить в какой-то треугольник триангуляции. Переберем третью вершину k (i<k<j) этого треугольника. Для данного k понятно, что ответ равен
L[i][k]+L[k][j]+d[i][k]+d[k][j],
где d[i][j] - расстояние между i-й и j-й вершинами. (После выбрасывания треугольника (i,j,k) мы получим два многоугольника от i до k и от k до j)
Итого получаем формулу
L[i][j]=min{i<k<j : L[i][k]+L[k][j]+d[i][k]+d[k][j]}.
Но при j=i+2 получится не совсем то (прибавятся стороны).
Поэтому инициализация L[i][i+2]=0 (1<=i<=N-2).
А ту формулу нужно использовать при j>i+2
Получается решение за O(N^3) с довольно маленькой константой.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо всем за помощь наконец-то написал эту задачу
→ Ответить