Abstract
Given a set of \(n\) axis-parallel rectangles in the plane, finding a maximum independent set (\(\mathrm {MIS}\)), a maximum weighted independent set (\(\mathrm {WMIS}\)), and a minimum hitting set (\(\mathrm {MHS}\)), are basic problems in computational geometry and combinatorics. They have attracted significant attention since the sixties, when Wegner conjectured that the duality gap, equal to the ratio between the size of \(\mathrm {MIS}\) and the size of \(\mathrm {MHS}\), is always bounded by a universal constant. An interesting case is when there exists a diagonal line that intersects each of the given rectangles. Indeed, Chepoi and Felsner recently gave a 6-approximation algorithm for \(\mathrm {MHS}\) in this setting, and showed that the duality gap is between 3/2 and 6. We consider the same setting and improve upon these results. First, we derive an \(O(n^2)\)-time algorithm for the \(\mathrm {WMIS}\) when, in addition, every pair of intersecting rectangles have a common point below the diagonal. This improves and extends a classic result of Lubiw, and gives a 2-approximation algorithm for \(\mathrm {WMIS}\). Second, we show that \(\mathrm {MIS}\) is NP-hard. Finally, we prove that the duality gap is between 2 and 4. The upper bound, which implies a 4-approximation algorithm for \(\mathrm {MHS}\), follows from simple combinatorial arguments, whereas the lower bound represents the best known lower bound on the duality gap, even in the general setting of the rectangles.
Similar content being viewed by others
Notes
Given a finite set of rectangles in the plane, the intersection graph is the graph with the rectangles as vertices, and two rectangles are adjacent if and only if they intersect.
We observe that the line \(D\) can be replaced by any decreasing bijective real function, so that the boundary of each \(r \in \mathcal {R}\) intersects the curve of that function in at most two points. By applying a suitable piecewise linear transformations on both coordinates, we can transform the rectangle set into one with the same intersection graph such that every rectangle is pierced by \(D\).
References
Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 400–409. IEEE, New York (2013)
Ahmadinejad, A., Zarrabi-Zadeh, H.: The maximum disjoint set of boundary rectangles. In: Proceedings of the Twenty Sixth Canadian Conference on Computational Geometry (2014)
Aronov, B., Ezra, E., Sharir, M.: Small-size \(\varepsilon \)-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)
Asano, T.: Difficulty of the maximum independent set problem on intersection graphs of geometric objects. In: 6th ICTAG (1991)
Caraballo, L.E., Ochoa, C., Pérez-Lantero, P., Rojas-Ledesma, J.: Matching colored points with rectangles. http://arxiv.org/abs/1309.3696 (2014)
Catanzaro, D., Chaplick, S., Felsner, S., Halldórsson, B.V., Halldórsson, M.M., Hixon, T., Stacho, J.: Max point-tolerance graphs. http://www.user.tu-berlin.de/chaplick/mpt.pdf (2013). Accessed Apr 2014
Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 892–901. Society for Industrial and Applied Mathematics, Philadelphia (2009)
Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373–392 (2012)
Chepoi, V., Felsner, S.: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46(9), 1036–1041 (2013)
Cibulka, J., Hladký, J., Kazda, A., Lidický, B., Ondráčková, E., Tancer, M., Jelínek, V.: Personal Communication (2011)
Fon-Der-Flaass, D.G., Kostochka, A.V.: Covering boxes by points. Discrete Math. 120(1), 269–275 (1993)
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133–137 (1981)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland, Amsterdam (2004)
Gyárfás, A., Lehel, J.: Covering and coloring problems for relatives of intervals. Discrete Math. 55(2), 167–180 (1985)
Kong, H., Ma, Q., Yan, T., Wong, M.: An optimal algorithm for finding disjoint rectangles and its applications to pcb routing. In: Proceedings of the Forty Seventh ACM/EDAC/IEEE Design Automation Conference, pp. 212–217 (2010)
Hixon, T.S.: Hook graphs and more: some contributions to geometric graph theory. Masters thesis, Technische Universität Berlin, Berlin (2013)
Hsiao, J.Y., Tang, C.Y., Chang, R.S.: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Inf. Process. Lett. 43(5), 229–235 (1992)
Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4(4), 310–323 (1983)
Károlyi, G.Y.: On point covers of parallel rectangles. Period. Math. Hung. 23(2), 105–107 (1991)
Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Lubiw, A.: A weighted min-max relation for intervals. J. Comb. Theory Ser. B 53(2), 151–172 (1991)
Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883–895 (2010)
Soto, J.A., Telha, C.: Jump number of two-directional orthogonal ray graphs. In: Integer Programming and Combinatorial Optimization, pp. 389–403. Springer, Berlin (2011)
Soto, M., Thraves, C.: (c-)And graphs—more than intersection, more than geometric. http://arxiv.org/abs/1306.1957 (2013)
Wegner, G.: Über eine kombinatorisch-geometrische frage Hadwiger und Debrunner. Isr. J. Math. 3(4), 187–198 (1965)
Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3(3), 351–358 (1982)
Acknowledgments
We thank Vít Jelínek for allowing us to include the lower bound example in Fig. 7, and Flavio Guíñez and Mauricio Soto for stimulating discussions. We also thank two anonymous reviewers whose many suggestions greatly improved the presentation of the paper. This work was supported by Núcleo Milenio Información y Coordinación en Redes ICM/FIC P10-024F and done while the second author was visiting Universidad de Chile. The third author was also supported by FONDECYT Grant 11110069, and the fourth author by FONDECYT Grant 11130266.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of a preliminary version of this work appears in the Proceedings of the 11th Latin American Theoretical Informatics Symposium, LATIN 2014.
Rights and permissions
About this article
Cite this article
Correa, J., Feuilloley, L., Pérez-Lantero, P. et al. Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity. Discrete Comput Geom 53, 344–365 (2015). https://doi.org/10.1007/s00454-014-9661-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-014-9661-y