Question

You are given a convex polygon P on n vertices in the plane (specified by their x and y coordinates). A triangulation of P is a collection of $\mathit{n}\mathbf{}\mathbf{-}\mathbf{}\mathbf{3}$diagonals of such that no two diagonals intersect (except possibly at their endpoints). Notice that a triangulation splits the polygon’s interior into $\mathit{n}\mathbf{}\mathbf{-}\mathbf{}\mathbf{2}$ disjoint triangles. The cost of a triangulation is the sum of the lengths of the diagonals in it. Give an efficient algorithm for finding a triangulation of minimum cost. (Hint: Label the vertices of P by 1,....,n, starting from an arbitrary vertex and walking clockwise. For $\mathbf{1}\mathbf{\le }\mathit{i}\mathbf{<}\mathit{j}\mathbf{\le }\mathit{n}$, let the subproblem $\mathit{A}\left(i,j\right)$denote the minimum cost triangulation of the polygon spanned by vertices $\mathit{i}\mathbf{,}\mathit{i}\mathbf{+}\mathbf{1}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathit{j}$.).

Short answer

Convex Polygon: A convex polygon is a close figure whose each interior angle is less than $180°$This means that no diagonal can be made which passes outside the boundary of polygon.

Step-by-step solution

Defining the Recursive Equation of Minimum Cost Triangulation

We will make our recursive equation in such a way that no diagonal cross eachother. For numbering, we will follow clockwise direction.

If $A\left(i,j\right)$denote minimum cost triangulation, where $i,j$are different vertices, Then $\left(i,i\right)=0$as we cannot make diagonal using same vertice.

Thus, Recursive Equation is:

localid="1657271470951" $\mathrm{A}\left(\mathrm{i},\mathrm{j}\right)=0\left\{\begin{array}{l}{\min }_{\mathrm{i}\le \mathrm{k}\le \mathrm{j}}\left\{\mathrm{A}\left(\mathrm{i},\mathrm{k}\right)+\mathrm{A}\left(\mathrm{k},\mathrm{j}\right)+{\mathrm{d}}_{\mathrm{i},\mathrm{k}}+{\mathrm{d}}_{\mathrm{k},\mathrm{j}}\right\}\\ 0;\mathrm{if}\mathrm{i}=\mathrm{j}\end{array}\right.$

Now it is important to define the length of diagonal(d). It is given as:

${\mathrm{d}}_{\mathrm{i},\mathrm{j}}=\left\{\begin{array}{l}\sqrt[2]{{\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}}\right)}^2+{\left({\mathrm{y}}_{\mathrm{i}}-{\mathrm{y}}_{\mathrm{j}}\right)}^2}\\ 0;\mathrm{otherwise}\end{array}\right.;\mathrm{if}\mathrm{j}-\mathrm{i}\ge 2$

Implementing Algorithm

The algorithm would be as follows:

$$\begin{gathered} for\left(i=0ton\right) \\ A\left(i,j\right)=0 \\ for\left(m=1ton-1\right) \\ for\left(i=1ton-m\right) \\ j=i+m \\ mi{n}_{i\le k\le j}\left\{A\left(i,j\right)+A\left(k,j\right)+d_{i,k}+d_{k,j}\right\} \end{gathered}$$

return$A\left(1,n\right)$

Analyse the Algorithm

Now, the outer for loop takes$0\left(n\right)$time to compute each of the entry of$A\left(i,j\right)$

The two nested loop takes $0\left(n^2\right)$time. So the effective time complexity will be$0\left(n^3\right)$.