Choose irregular polygons from a list of irregular polgyons, to cover a quadrilateral

Question

I have a large set of given irregular convex polygons (with between 3 and 6 sides). I need to write code to chose n of these polygons such that when combined they completely cover a given quadrilateral. The polygons in the given list overlap enough such that any given point in the quadrilateral will also be contained in several polygons -- I just need to find a subset that does it.

Ideally, I would like to minimise n, but this is not a hard requirement and I don't need to rigorously prove anything about my method.

I can think of a few naiive ways to do this. Here's one:

1. create a regular grid of points filling the quadrilateral
2. for each grid point, randomly choose a polygon which contains tjat point
3. merge the selected polygon and check if the quadrilateral is fully contained within the merged polygon
4. if not, start again from step 1 using a denser grid

However, I expect that the computational geometry people have better ways to do this. I'd appreciate if anyone can suggest an algorithm or point me to a paper.

Answer 1

This doesn't really help, but perhaps sets some boundaries:

• "Covering a polygon (which may contain holes) with convex polygons is NP-hard."

So you are into the realm of approximation algorithms.

A greedy approach is to compute the arrangement of cells determined by your collection of polygons, recording the depth of coverage of each cell of the target quadrilateral. Then select a polygon in the most shallowly covered cell, update all the cell coverages, and repeat.