I am looking for a way to approximate a geographic region with a few bounding boxes. I know I can get a single box to cover the whole region, but some of my shapes are quite strange (gerrymandered, in some cases).
I'd like to know if there's a way to approximate a shape as a (small) collection of axis-aligned rectangles to make a tighter collection of bounding boxes.
For example, I know I can draw a rectangular box around a roughly "C" shaped region, but I can make a much better approximation with 3 rectangles like so:
+--------------+ | | +----+---------+ | | | | | +~~+--------+ +-+~~+ | +-----------+
- The rectangles should contain the entire original shape.
- It's fine if the rectangles overlap.
- I'd really like to stay under 10 rectangles. (Maybe an increased penalty for each additional rectangle?)
- I'd also like to have under 25% of the original shape's area as extraneously included by the rectangles, but if it takes too many shapes to do so, I'll go with fewer shapes.
Is there a recognized method for doing this to arbitrary shapes? To certain classes of shapes?