CGAL users discussion list

["Laurent Rineau (CGAL/GeometryFactory)" <>]

Le lundi 03 juin 2013 20:48:30 Winnie a écrit :
> 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.

Re-read more carefully the paper. The decision problem of the paper is the 
following:

"A set, V, of points in the plane is triangulated by a subset T, of the 
straight-line segments whose endpoints are in V, if T is a maximal subset 
such 
that the line segments in T intersect only at their endpoints. [...] 
Secondly, 
we show that the problem of determining the existence of a triangulation, in 
a 
given subset of the line segments whose endpoints are in V, is NP-Complete."

The edges of a constrained Delaunay triangulation are in a superset of the 
constraint segments, and not in a subset.

-- 
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/