Technical Report CS0541

TR#:CS0541
Class:CS
Title: Covering Polygons With Squares
Authors: R. Bar-Yehuda and E. Ben-Chanoch
PDFCS0541.pdf
Abstract: An orthogonal polygon is one that has only horizontal and vertical edges. A polygon is simple if it has no holes. We study the problem of covering a polygon with minimum number of squares, possibly overlapping, all internal to the polygon. This problem has applications in VLSI and computer vision.

First, we study 'the problem for simple polygons. No algorithm polynomial in the number of polygon vertices n, and the output size OPT, was previously known. Our main result is an O(nlogn+OPT) algorithm. Recently, Aupperle, Conn, Keil, and O'Rourke presented an O(p^15) algorithm, where p is the number of pixels in a bit-map representation. Observe that p > n and may even be exponential in n. Moreover, a simple implementation of our algorithm to bit-map representation, yields 0 (P) time complexity.

We also study non-simple polygons. Aupperle et. al. proved that this problem is NP-Hard. Thus, it is natural to look for approximation algorithms. There are some local-minima hueristic algorithms in the literature. We show that any local-minima algorithm is a factor 4 approximation. In addition, we present a factor 2 approximation algorithm. Denote by h, the number of holes in the polygon. The time complexity of our algorithm is O(nlogn+OPT+h(logn)^3). In fact our algorithm guarantees a cover of size<=OPT+h.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1989/CS/CS0541), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion
admin