Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Is there an algorithm similar to the Delaunay triangulation which can organize a set of points into a set of four sided polygons instead of triangles?

share|cite|improve this question
There are a number of algorithms for quadrilateral mesh generation. See this and this and this for instance. – J. M. Sep 2 '11 at 12:05
Thanks J-M that is a lot to read ! Is there any specific techniques which you can think of given a set of points in a 2D space? – Arthur Mamou-Mani Sep 2 '11 at 15:53
I've read those, but I haven't experimented on them. You will have to experiment for yourself. – J. M. Sep 2 '11 at 15:54
up vote 1 down vote accepted

I don't know of any quadrangulation having similar properties to a Delaunay triangulation, but you can always convert a triangulation to a quadrangulation by adding additional points, called Steiner points. See the first section of for instance.

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.