Welcome to MathOverflow

Question

2

1

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?

edited Jun 16 2010 at 0:03

Gerry Myerson
15.7k●1●47●87

asked Jun 15 2010 at 19:28

firstTimeUser
21●2

	What specific quantity are you trying to minimize? Total number of polygons? – S. Carnahan♦ Jun 15 2010 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 2010 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 2010 at 0:51

David Eppstein · Answer 1 · 2010-06-16 04:44:37Z UTC

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.

split polygon into minimum amount of rectangles and triangles

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.