Non-delaunay triangulation of a set of points and its convex hull boundary

Question

I have a set of n random points on a 2D plane, and its convex hull boundary. Some points lie interior to the convex hull boundary. I want to triangulate this in a non-delaunay random fashion, such that it conforms to the points interior to the convex hull boundary (the points inside are vertices of the triangulation) and the convex hull boundary itself. Any ideas would be appreciated.

Answer 1

I think I might have found a solution.

Given the convex-hull boundary, I can find out all the points that are purely inside the convex-hull boundary. Next, I find the points on the convex hull boundary with the maximum and minimum x-coordinates. Next, I sort all the internal points by their x-coordinates. If these points exist in an appropriate data structure, such as a Doubly Connected Edge List, I add edges between consecutive points in the x-coordinated sorted order. Further I connect the left most point of the convex hull boundary to the left most point of the internal set, and the right most point of the convex hull boundary to the right most point of the internal set. This forms 2 monotone polygons that each can be triangulated in O(n).