Abstract
We consider the problem of covering arbitrary polygons, without any acute interior angles, using a preferably minimum number of squares. The squares must lie entirely within the polygon. Let P be an arbitrary input polygon, with n vertices, coverable by squares. Let μ(P) denote the minimum number of squares required to cover P. In the first part of this paper we present an algorithm which guarantees a constant (14) approximation factor running in O(n 2+μ(P)) time. As a corollary we obtain the first polynomial-time, constant-factor approximation algorithm for “fat” rectangular coverings. In the second part we show an O(n log n+μ(P)) time algorithm which produces at most 11n+μ(P) squares to cover P. In the hole-free case this algorithm runs in linear time and produces a cover which is within an O(α(n)) approximation factor of the optimal, where α(n) is the extremely slowly growing inverse of Ackermann's function. In parallel our algorithm runs in O(log n) randomized time using O(max(μ(P), n)) processors.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L.J. Aupperle, H.E. Conn, J.M. Keil and J. O'Rourke, Covering Orthogonal Polygons with Squares, 26th Annual Allerton Conference on Communication, Control and Computation, 1988.
R. Bar-Yehuda and E. Ben-Hanoch, A Linear-Time Algorithm for Covering Simple Polygons with Similar rectangles, International Journal of Computational Geometry & Applications, vol. 6, no 1, 1996.
B.M. Chazelle, Computational Geometry and Convexity, Ph.D. Thesis, Dept. Comp. Sci., Yale University, New Haven, CT, 1979. Carnegie-Mellon Univ. Report CS-80-150.
J. Snoeyink, C.A. Wang and F. Chin, Finding the Medial Axis of a Simple Polygon in Linear-Time, ISAAC '95, Cairns, Australia, 1995 (LNCS 1006 Springer-Verlag).
C. Levcopoulos and J. Gudmundsson, Close Approximation of Minimum Rectangular Coverings, FST&TCS-16, Hyderabad, India, 1996 (LNCS, Springer-Verlag).
C. Levcopoulos and J. Gudmundsson, Approximation Algorithms for Covering Polygons with Squares and Similar Problems, LU-CS-TR:96-181, Dept. of Comp. Sci., Lund University, 1996.
A. Hegedüs, Algorithms for covering polygons by rectangles, Computer Aided Design, vol. 14, no 5, 1982.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel Sequences and of Generalized Path Compression Schemes, Tech. Report 84-011, The Eskenasy Institute of Comp. Sci., Tel Aviv University, August 1984.
D.G. Kirkpatrick, Efficient computation of continuous skeletons, 20th Annual IEEE Symposium on Foundation of Computer Science, 1979.
J.M. Keil and J.-R. Sack, Minimum Decompositions of Polygonal Objects, Machine Intelligence and Pattern Recognition vol. 2: Computational Geometry, pp. 197–215, Elsevier Science Publishers B.V., 1985.
C. Levcopoulos, A Fast Heuristic for Covering Polygons by Rectangles, FCT'85, Cottbus, GDR, 1985 (LNCS 199, Springer-Verlag).
C. Levcopoulos, Improved Bounds for Covering General Polygons with Rectangles, FST&TCS-7, Pune, India, 1987 (LNCS 287, Springer-Verlag).
D. Morita, Finding a Minimal Cover for Binary Images: an Optimal Parallel Algorithm, Tech. Report No. 88-946, Dept. of Comp. Sci., Cornell University, 1988.
J. O'Rourke and K.J. Supowit, Some NP-hard Polygon Decomposition Problems, IEEE Transactions on Information Theory, vol. IT-29, pp. 181–190, 1983.
F.P. Preparata and M.I. Shamos, Computational Geometry, New York, Springer-Verlag, 1985.
S. Rajasekaran and S. Ramaswami, Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane and Related Problems, In Proc. ACM Symposium on Computational Geometry, Stony Brook, New York, 1994.
D.S. Scott and S.S. Iyengar, TID: a Translation Invariant Data Structure for Storing Images, Comm. of the ACM, vol. 29, no. 5, 1986.
A. Wiernik, Planar Realization of Nonlinear Davenport-Schinzel Sequences by Segments, 27th IEEE Symposium on Computer Science, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Levcopoulos, C., Gudmundsson, J. (1997). Approximation algorithms for covering polygons with squares and similar problems. In: Rolim, J. (eds) Randomization and Approximation Techniques in Computer Science. RANDOM 1997. Lecture Notes in Computer Science, vol 1269. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63248-4_3
Download citation
DOI: https://doi.org/10.1007/3-540-63248-4_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63248-1
Online ISBN: 978-3-540-69247-8
eBook Packages: Springer Book Archive