# Polygon rectangulation wrap up

Tying up loose ends from my three posts in December about rectangulation of orthogonal polygons.

1. Derrick Stolee requested in a comment a resolution of the computational complexity of the 3D version of the problem of decomposing a shape into the minimum number of rectangles.  I found a reference that proves the problem is NP-complete, by directly reducing the problem to a variant of 3SAT.  The diagrams of the gadgets used are pretty cool — the gadgets look like children’s toys used to build 3D structures.  Rectangular partition is polynomial in two dimensions but NP-complete in three, by Victor J. Dielissen and Anne Kaldewaij, Information Processing Letters, April 1991.
2. The survey Polygon Decomposition by J. Mark Keil (1996) has much more information on exact algorithms for rectangulation, triangulation, and problems I did not mention at all, like covering.
3. There is an extensive literature on approximation algorithms for finding a minimum-length rectangulation of an orthogonal polygon with holes.  (The problem is NP-complete even for the case where the polygon is a rectangle and its interior holes are points.)  I can recommend the survey Minimum Edge-Length Rectangular Partitions, by Gonzalez and Zheng (in Handbook of Approximation Algorithms and Metaheuristics, 2007).

Victor J. Dielissen, & Anne Kaldewaij (1991). Rectangular partition is polynomial in two dimensions but NP-complete in three Information Processing Letters, 38 (1), 1-6 : 10.1016/0020-0190(91)90207-X

About these ads

### One response to “Polygon rectangulation wrap up”

1. amit erez

Interesting variant of rectilinear polygon coverage which was not mentioned is the one where a coverage made of maximal rectangles is looked for. this is usefull for some interesting VLSI CAD problems. for example – placement and design rule checking