Take the 2-minute tour ×
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.

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|improve this question
2  
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

1 Answer 1

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 http://www.cs.mcgill.ca/~cs507/projects/1998/rachelp/ for instance.

share|improve this answer

Your Answer

 
discard

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.