CGAL users discussion list

[Winnie <>]

Hi list,

if I understand it right, the CGAL implementation claims to find a 
constrained triangulation in polynomial time [1]. Given that the 
constraints don't intersect, does this also claim that there always 
exists a triangulation?

If I understand Lloyd [2] [3] right, he claims that the decision whether 
a constrained triangulation exists (he calls it TRI) is already NP-complete.

But... if I can find a constrained triangulation in polynomial time, 
wouldn't that also solve the decision problem whether there exists a 
triangulation?

I hope somebody of you can help me out of this. Thanks in advance!

Winnie

[1] 
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2_ref/Class_Constrained_triangulation_2.html#Function_void_insert_constraint6Point_a+_Point_b9;
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4567947
[3] https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Lloyd.pdf