I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers to useful references. I'm interested in feasible algorithms for the following problem.Input: A connected set of points (shape) in $\mathbb{Z} \times \mathbb{Z}$.  Output: A partition of the shape into rectangles, such that the rectangles do not overlap one another, and they cover only the shape, no empty space.I'm interested in finding the minimum number of rectangles, the best set of rectangles for any notion of best, whether this problem becomes easier or harder for different classes of shapes.Thank you. :-)
Partitioning a connected shape into rectangles
reference request;cg.comp geom
David Eppstein gave an excellent answer for this question here on MathOverflow (responding to a question for which it is not quite as good an answer). To summarize, there is a polynomial-time algorithm for finding the minimum number of rectangles.