V. S. Anil Kumar
- 1.P. Berman and B. Dasgupta. Approximating Rectilinear Polygon Cover Problems. Proceedings of dth Canadian Conference on Computational Geometry, 19927 pp. 229-2;35.Google Scholar
- 2.H. Br6nnimann, M. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension. Discrete Comput. Geom., 142 19957 pp. 263-279.Google Scholar
- 3.S. ChaJken, D.J. Kleitman, M. Saks and J. Shearer. Covering Regions by Rectangles. SIAM J. Algebraic and Discrete Methods, Vol. 2, 4, 198t, pp. 394-410.Google Scholar
- 4.Y. Cheng, S.S. Iyengax and R.L. Kashyap. A New Method for Image compression using Irreducible Covers of Maximal Rectangles. IEEE 7h~nsactions on Software Engineering, Vol. 14, 5, 1988, pp. 651-658. Google ScholarDigital Library
- 5.J.C. Cutberson and R.A.Reckhow. Covering Polygons is Hard. Journal o} Algorithms, 17, 1994, pp. 2-44. Google ScholarDigital Library
- 6.D.S. Franzblau. Performance Guarantees on a Sweep Line Heuristic for Covering Rectilinear Polygons with Rectangles. SIAM J. Discrete Math., Vol. 2, 3, 1989, pp. 307-321. Google ScholarDigital Library
- 7.D.S. Franzblau and D.J. Kleitman. An Algorithm for Constructing Regions with Rectangles. Information and Control, 63, 1984, pp. 164-189. Google ScholarDigital Library
- 8.A. Hegediis. Algorithms for Covering Polygons with Rectangles. Computer Aided Geom. DeMgrq 14, {982, pp. 257-260.Google Scholar
- 9.D.S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computing and Systems Sciences, 9, 1974, pp. 256-278.Google ScholarDigital Library
- 10.J.M. KeiI. Minimally Covering a Horizontally Convex Ortlaogonal Polygon. Proceedings of 2nd A CM Symposium on Computational Geometry, 1986, pp. 43-51. Google ScholarDigital Library
- 11.C. Levcopoulos. On Covering Regions with Minimum Number of Rectangles. Proceedings of International Workshop on Par. Comp. and VLSI, I984.Google Scholar
- 12.C. Levcopoulos. A Fast Heuristic for Covering Polygons by Rectangles. Proceedings of Fundamental, of Computer Theory, 1985. Google ScholarDigital Library
- 13.C. Levcopoulos. Improved Bounds for Covering General Polygons by Rectangles. Proceedings of 6th Foundations of Software Tech. and Theoretical Comp. Sc., LNCS 287, 1987. Google ScholarDigital Library
- 14.C. Levcopoulos and J. Gudmundsson. Close Approximations of Minimum RectanguIar Covering. Proceedings of l 6th Foundations of Software Tech. and Theoretical Comp. Sc., LNCS 1180, 1996, pp. 135-146. Google ScholarDigital Library
- 15.C. Levcopoulos and J. Gudmundsson. Approximation Algorithms for Covering Polygons with Squares and Similar Problems. Technical Report, Lund University.Google Scholar
- 16.L. Lovasz. On the Ratio of Optimal.Integral and Fractional Covers. Journal of Discrete Mathematics, 13, 1975, pp. 383-390.Google ScholarDigital Library
- 17.R.Raz and S.Sa~a. A Sub-Constant Error- Probability Low-Degree test and a Sub-Constant Error-Probability PCP Characterization of NP. Proceedings of the A CM Symposium on Theory of Computing, 1997. Google ScholarDigital Library
- 18.C. Lund and M. Yann~~. On the Hardness of Approximating Minimization Problems. Proceedings of ~Sth A CM Symposium on Theory of Computing, I993, pp. 286-293. Google ScholarDigital Library
- 19.W.J. Masek. Some NP-Comptete Set Covering Problems, Manuscript, MIT, 1979.Google Scholar
Index Terms
- Covering rectilinear polygons with axis-parallel rectangles
Recommendations
Covering Rectilinear Polygons with Axis-Parallel Rectangles
We give an $O(\sqrt{\log n})$ factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm for this problem with an $o(\log n)$ approximation ...
Covering rectilinear polygons by rectangles
Three approximation algorithms to cover a rectilinear polygon that is neither horizontally nor vertically convex by rectangles are developed. All three guarantee covers that have at most twice as many rectangles as in an optimal cover. One takes O ( n ...
Comments