Minimum Cost Polygon Triangulation (การสามเหลี่ยมมุมน้อยที่สุด)

เมื่อวาดเส้นทแยงมุมที่ไม่ทับซ้อนในรูปหลายเหลี่ยมจนได้สามเหลี่ยม เรียกว่า Triangulation

Cost ของ triangulation = ผลรวมของ perimeter (เส้นรอบรูป) ของสามเหลี่ยมทุกอัน ต้องการหา triangulation ที่มี cost น้อยที่สุด

ตัวอย่าง Input และ Output

Input: จุดของรูปหลายเหลี่ยม 5 จุด
{(0,0), (1,0), (2,1), (1,2), (0,2)}

Output: The minimum cost: 15.3006

อัลกอริทึม Dynamic Programming

ฟังก์ชัน minCost(polygon, n)

แนวคิด: Interval DP

กำหนด table[i][j] = minimum cost ของการ triangulate polygon จาก vertex i ถึง j

Euler's Formula สำหรับ Polygon:

Polygon n จุด ต้องมีสามเหลี่ยม n-2 อัน และเส้นทแยง n-3 เส้น

ขั้นตอน:

1. ถ้า n < 3 → คืน 0 (ไม่สามารถ triangulate ได้)
2. สร้างตาราง table[n][n]
3. for gap = 0 ถึง n-1 (ความยาวช่วง):
   • for i = 0, j = gap; j < n; i++, j++:
     • ถ้า j < i+2 (น้อยกว่า 3 จุด) → table[i][j] = 0
     • มิฉะนั้น table[i][j] = INF
     • for k = i+1 ถึง j-1 (ลอง vertex กลาง):
       • val = table[i][k] + table[k][j] + cost(i, j, k)
       • cost(i,j,k) = perimeter ของสามเหลี่ยม (i,j,k)
       • อัปเดต table[i][j] = min(table[i][j], val)
4. คืน table[0][n-1]

ตัวอย่างโค้ด C++

#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define MAX 1000000.0
using namespace std;

struct Point { int x, y; };

double dist(Point p1, Point p2) {
    return sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
}

double cost(Point triangle[], int i, int j, int k) {
    Point p1 = triangle[i], p2 = triangle[j], p3 = triangle[k];
    return dist(p1,p2) + dist(p2,p3) + dist(p3,p1);
}

double minimumCost(Point polygon[], int n) {
    if (n < 3) return 0;
    double table[n][n];

    for (int gap = 0; gap < n; gap++) {
        for (int i = 0, j = gap; j < n; i++, j++) {
            if (j < i+2)
                table[i][j] = 0.0;
            else {
                table[i][j] = MAX;
                for (int k = i+1; k < j; k++) {
                    double val = table[i][k] + table[k][j] + cost(polygon,i,j,k);
                    if (table[i][j] > val)
                        table[i][j] = val;
                }
            }
        }
    }
    return table[0][n-1];
}

int main() {
    Point points[] = {{0,0}, {1,0}, {2,1}, {1,2}, {0,2}};
    int n = 5;
    cout << fixed << setprecision(4);
    cout << "The minimum cost: " << minimumCost(points, n);
    return 0;
}

Output

The minimum cost: 15.3006

ความซับซ้อน

• Time: O(n³) - gap, i, k ทั้งสามลูป
• Space: O(n²) - ตาราง DP

หมายเหตุ

ปัญหานี้คล้าย Matrix Chain Multiplication โครงสร้าง DP เหมือนกัน (Interval DP)