Complexities of efficient solutions of rectilinear polygon cover problems. (English) Zbl 0869.68058
Summary: The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon of \(n\) vertices has to be covered with the minimum number of rectangles included in the polygon. In particular, we consider covering the entire interior, the boundary, and the set of corners of the polygon. These problems have important applications in storing images and in the manufacture of integrated circuits. Unfortunately, most of these problems are known to be NP-complete. Hence it is necessary to develop efficient heuristics for these problems or to show that the design of efficient heuristics is impossible. In this paper, we show: (a) The corner cover problem is NP-complete. (b) The boundary and the corner cover problem can be approximated within a ratio of 4 of the optimum in \(O(n\log n)\) and \(O(n^{1.5})\) time, respectively. (c) No polynomial-time approximation scheme exists for the interior and the boundary cover problems, unless P\(=\)NP.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
rectilinear polygon cover problemReferences:
| [1] | S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and Hardness of Approximation Problems.Proc. 33rd IEEE Symp. on Foundations of Computer Science (FOCS) 1992, pp. 14-23. · Zbl 0977.68539 |
| [2] | P. Berman and B. DasGupta. Results on Approximation of the Rectilinear Polygon Cover Problems. Tech. Rep. #CS-92-06, Pennsylvania State University, June, 1992. |
| [3] | Berman, P.; Schnitger, G., On the Complexity of Approximating the Independent Set Problem, Inform. and Comput., 96, 77-94 (1992) · Zbl 0804.90121 · doi:10.1016/0890-5401(92)90056-L |
| [4] | Chaiken, S.; Kleitman, D. J.; Saks, M.; Shearer, J., Covering Regions by Rectangles, SIAM J. Algebraic Discrete Methods, 2, 394-410 (1981) · Zbl 0506.05022 |
| [5] | H. E. Conn and J. O’Rourke. Some Restricted Rectangle Covering Problems. Tech Rep. JHU-87/13, Johns Hopkins University, Baltimore, MD, 1987. Also appeared inProc. Allerton Conference, 1987, pp. 898-907. |
| [6] | Corman, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), Cambridge, MA: MIT Press, Cambridge, MA · Zbl 1158.68538 |
| [7] | Culberson, J. C.; Reckhow, R. A., Covering Polygon Is Hard, J. Algorithms, 17, 2-44 (1994) · Zbl 0811.68089 · doi:10.1006/jagm.1994.1025 |
| [8] | Franzblau, D. S., Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles, SIAM J. Discrete Math., 2, 307-321 (1989) · Zbl 0673.05018 · doi:10.1137/0402027 |
| [9] | Franzblau, D. S.; Kleitman, D. J., An Algorithm for Covering Polygons with Rectangles, Inform. and Control, 63, 3, 164-189 (1984) · Zbl 0591.68073 · doi:10.1016/S0019-9958(84)80012-1 |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability—A Guide to the Theory of NP-Completeness (1979), San Francisco, CA: Freeman, San Francisco, CA · Zbl 0411.68039 |
| [11] | Hopcroft, J. E.; Karp, R. M., Ann^5/2 Algorithm for Maximum Matching in Bipartite Graphs, SIAM J. Comput., 2, 225-231 (1979) · Zbl 0266.05114 · doi:10.1137/0202019 |
| [12] | Lubiw, A., Ordering and Some Combinatorial Optimization Problems with Some Geometric Applications (1985), Ontario: University of Waterloo, Ontario |
| [13] | Lubiw, A., The Boolean Basis Problem and How to Cover Polygons by Rectangles (1988), Ontario: University of Waterloo, Ontario |
| [14] | W. J. Masek. Some NP-Complete Set Covering Problems. Unpublished manuscript, MIT, Cambridge, MA. Referenced in [10]. M. R. Garey and D. S. Johnson.Computers and Intractability—A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979. · Zbl 0411.68039 |
| [15] | Mead, C.; Conway, L., Introduction to VLSI Systems (1980), Reading, MA: Addison-Wesley, Reading, MA |
| [16] | Motwani, R.; Raghunathan, A.; Saran, H., Perfect Graphs and Orthogonally Convex Covers, SIAM J. Discrete Math., 2, 371-392 (1989) · Zbl 0674.05070 · doi:10.1137/0402033 |
| [17] | T. Ohtsuki. Minimum Dissection of Rectilinear Polygons.Proc. IEEE Symp. on Circuits and Systems, 1982, pp. 1210-1213. |
| [18] | O’Rourke, J.; Supowit, K. J., Some NP-Hard Polygon Decomposition Problems, IEEE Trans. Inform. Theory, 29, 181-190 (1983) · Zbl 0501.68036 · doi:10.1109/TIT.1983.1056648 |
| [19] | Pagli, L.; Lodi, E.; Luccio, F.; Mugnai, C.; Lipski, W., On Two-Dimensional Data Organization 2, Fund. Inform., 2, 211-226 (1979) · Zbl 0421.68091 |
| [20] | Papadimitriou, C. H.; Yannakakis, M., Optimization, Approximation and Complexity Classes, J. Computer System Sci., 43, 425-440 (1991) · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
