Skip to content
Prev 1567 / 29559 Next

Function to cover polygons by rectangles

Christoph Hofer wrote:
Just use one big rectangle. Big enough to cover the polygon. Job done.

  Okay, I'll assume from now on you want to divide the polygon 
internally into rectangles.
This problem doesn't seem well-posed just yet. You can't cover some 
polygons with a finite number of rectangles, so you need to specify when 
to stop - at a given number of rectangles or when X% of the polygon is 
covered? Also, do you want to restrict your rectangles to be aligned to 
some axis, or can each rectangle have any rotation?

  This looks like a hard problem. I'm just trying to think about the 
simplest non-trivial case I can come up with, filling an equilateral 
triangle. How do you stick one rectangle in an equilateral triangle and 
maximise its area?[1] Then for two rectangles, do you start with the 
best one-rectangle solution and then add another to fill in a gap? Or is 
the best solution two completely new rectangles?

  Now, for a general, complicated, concave polygon... Ahhhh I give up.

  Barry

[1] I think for a equilateral triangle of side 2 the best single 
rectangle is a rectangle of side (1,sqrt(3)) aligned centrally and 
adjacent to one side. I think I've just convinced myself that for two 
rectangles you stick a similar rectangle into the remaining equilateral 
triangle portion. If you continue, at some point you'll want to start 
filling in the semi-equilateral triangle pieces left by the first 
rectangle...