Base case: (an edge is not a polygon, no triangulation needed). Iterate by polygon size (number of vertices in the sub-polygon). For each interval where , try all intermediate vertices . Time: , Space: . Same complexity as Matrix Chain Multiplication. The base case is edges (two adjacent vertices), which need no triangulation. Build up from there.
Time complexity: .
Space complexity: .