Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
Author:
- D. S. FranzblauDFD. S. Franzblau
- 1 August 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 2 (3) , 307-321
Abstract
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.
Keywords
This publication has 19 references indexed in Scilit:
- The Boolean Basis Problem and How to Cover Some Polygons by RectanglesSIAM Journal on Discrete Mathematics, 1990
- An algorithm for covering polygons with rectanglesInformation and Control, 1984
- A minimax theorem on intervalsJournal of Combinatorial Theory, Series B, 1984
- Covering polygons with minimum number of rectanglesLecture Notes in Computer Science, 1984
- Algorithms for covering polygons by rectanglesComputer-Aided Design, 1982
- The power of non-rectilinear holes1982
- Covering Regions by RectanglesSIAM Journal on Algebraic Discrete Methods, 1981
- Decomposing a polygon into its convex parts1979
- Graph Theory with Applications1976
- Approximation algorithms for combinatorial problemsJournal of Computer and System Sciences, 1974