Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
Deborah S. Franzblau · SIAM Journal on Discrete Mathematics · 1989
Finding the minimum number of rectangles required to cover a rectilinear or orthogonal polygon, where overlapping of rectangles is allowed, is one of several well-known, hard geometric decomposition problems. This paper reports the first results known that give worst-case performance bounds for an approximation algorithm for this problem. It is proved that partitioning the polygon into rectangles (with no overlapping) produces at most $2\theta + h - 1$ rectangles, where $\theta $ is the minimum number of rectangles in a cover, and h is the number of holes. Examples are also given in which this bound is tight. The proof is based on counting arguments, and on Euler’s formula for a planar graph. This paper shows that extending rectangles vertically and deleting duplicates produces at most $O(\theta \log \theta )$ rectangles. For the proof, geometric constraints are used to construct a large an-tirectangle, a set of points with no two contained in the same rectangle. This algorithm has an $O(n\log n)$ implementation using balanced trees, where n is the number of vertices.