Algorithm for completing a partial triangulation (Constrained Triangulation)

Question

Given a set of points in a plane and an incomplete triangulation of the convex hull of the points (only some edges are given), I'm looking for an algorithm to complete the triangulation (the initial given edges should remain fixed). You can assume that it's possible to complete the partial triangulation but it'd be great if you could also suggest an algorithm for checking that too.

UPDATE" You're given a convex hull of a set of points R^2, which is basically a polygon with some points inside it. We want to triangulate the set of points which is a straightforward matter on itself, but you're also given some edges that any triangulation that you come up with should use those edges."

Answer 1

Perhaps this is a naive answer, but can't you just use a constrained delaunay triangulation? Add the known edges as constraints.

CGAL has a nice implementation. The tool triangle has similar features and is easier to get started with, but has (perhaps) a little less flexibility.