Recently, I was asked to design an algorithm that counts the number of triangulations in a simple polygon without Steiner points. This is pretty simple to do in $O(n^3)$ time using dynamic programming, where $n$ is the number of vertices in the polygon. However, I would like to know if there is an $O(n^{3-\epsilon})$ algorithm for this problem. I am unable to find a better algorithm in the literature, nor can I find a lower bound. Any references would be appreciated.

  • $\begingroup$ Can you edit the question to show the $O(n^3)$ algorithm? Is it the following? Set $A(i,k)=0$ if vertices $v_i,v_j$ aren't mutually visible, otherwise $A(i,k)=A(i,k-1)+A(i+1,k)+\sum_{j=i+2}^{k-2} A(i,j) A(j,k)$; compute all $A(i,k)$ for all $i,k$, then output $A(0,n-1)$. Taken from P. Epstein & J.-R. Sack, Generating Triangulations at Random, ACM Trans. Modeling & Computer Simulation 1994. That paper also relates it to a graph problem. $\endgroup$ – D.W. Oct 15 '16 at 10:35
  • $\begingroup$ Yes, it is indeed that algorithm. $\endgroup$ – user340082710 Oct 15 '16 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.