Tying up loose ends from my three posts in December about rectangulation of orthogonal polygons.
- 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.
- 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.
- 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
Nanoexplanations 
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