MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained triangulations is the discovery of edges which are intersected by the constraint, removing them, and retriangulating the hole.

AFAIK the optimal time bound for 2D constrained triangulation is o( n log n ), where n is the number of input vertices. That's what Paul Chew achieved in his paper "Constrained Delaunay Triangulations" from 1987 (he described divide and conquer algorithm, which looks difficult to implement in practice BTW). I would like to stay within that bound. But I would like to know an algorithm which is asymptotically worse if it is also much simpler.

Numerical robustness is not an issue for me.


The input is a Planar straight-line graph. In my particular case the graph describes a polygon with holes, so it has no unconnected vertices - then it would be a list of vertices describing the outer boundary of the polygon and the boundaries of the holes.

As output I would like to have a mesh - a collection of triangles which are represented by 3 indices into an array of vertices.

share|cite|improve this question
Please explain in more detail what is your input and your desired output. – Neil Strickland Apr 23 '12 at 12:03

This does not directly answer your question, but the easiest implementation by far is to use one that already exists. Jonathan Shewchuck has written high-quality contrained Delaunay triangulation code in C++, and makes it easily available through his Triangle web page. It is fast; he quotes a runtime of 21 sec for 1,000,000 vertices.

If you want to use an inefficient algorithm, you could dispense with all efficient data structures, and use linear search whenever looking for an item. This will simplify the code.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.