91影视

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}鈮�\mathrm{k}鈮�\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}鈮�2$

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鈮�k鈮�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)$

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)$.