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. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s