Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi is there an algorithm which cuts a polygon into a minimum amount of preferably rectangles and where not possible (e.g. edges) into triangles?

share|improve this question
    
What specific quantity are you trying to minimize? Total number of polygons? –  S. Carnahan Jun 15 '10 at 19:47
    
You are probably looking for a space partititioning algorith (en.wikipedia.org/wiki/Space_partitioning) in computational geometry. Perhaps the equivalent of a Delaunay triangulation but with rectangles (en.wikipedia.org/wiki/Delaunay_triangulation) –  SandeepJ Jun 15 '10 at 20:33
    
Another possible interpretation of the question would be to partition a polygon into a minimum number of pieces, each of which is either a triangle or a rectangle. My guess is that this version is a difficult problem. –  Joseph O'Rourke Jun 16 '10 at 0:51
add comment

1 Answer

I'm not sure what you mean about the triangles, but if a polygon has all its sides axis-parallel, it is possible to find a partition into the minimum possible number of rectangles in polynomial time. The idea is to find the maximum number of disjoint axis-parallel diagonals that have two concave vertices as endpoints, split along those, and then form one more split for each remaining concave vertex. To find the maximum number of disjoint axis-parallel diagonals, form the intersection graph of the diagonals; this graph is bipartite so its maximum independent set can be found in polynomial time by graph matching techniques.

This method comes from several independent papers:

  • W. Lipski, Jr., E. Lodi, F. Luccio, C. Mugnai, and L. Pagli. On two-dimensional data organization II. Fundamenta Informaticae, 2:245–260, 1979.
  • T. Ohtsuki. Minimum dissection of rectilinear regions. In Proc. IEEE Int. Symp. Circuits and Systems, pages 1210–1213, 1982.
  • L. Ferrari, P. V. Sankar, and J. Sklansky. Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing, 28(1):58–71, 1984.

It's described in more detail in section 3 of my survey paper arXiv:0908.3916.

share|improve this answer
add comment

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.