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

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

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

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

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

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

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

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

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

UPD. На фоне этого, мой коммент можно не читать.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +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) с довольно маленькой константой.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня возник вопрос, почему найменьшая триангуляция состоит только из хорд между вершинами треугольника?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я думаю по определеию
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Триангуляция не всегда разбивает многоугольник на n-2 треугольника. Пример: триангуляция Делоне. С другой стороны, судя по всему, действительно выгоднее разбивать именно так, интересно, почему.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Триангуляция множества точек по определению должна брать вершины для треугольников только из данного набора точек (плюс еще другие условия). Т.е. для выпуклого N-улольника мы всегда будем иметь N-2 треугольника. Триангуляция Делоне не исключение.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Хм, действительно. Ну, тогда вот тут указывают, что одно из пониманий допускает добавление точек.
            → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо всем за помощь наконец-то написал эту задачу
→ Ответить