Skip to main content
Log in

Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Notes

  1. 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.

  2. 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

  1. 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)

  2. Ahmadinejad, A., Zarrabi-Zadeh, H.: The maximum disjoint set of boundary rectangles. In: Proceedings of the Twenty Sixth Canadian Conference on Computational Geometry (2014)

  3. Aronov, B., Ezra, E., Sharir, M.: Small-size \(\varepsilon \)-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  4. Asano, T.: Difficulty of the maximum independent set problem on intersection graphs of geometric objects. In: 6th ICTAG (1991)

  5. Caraballo, L.E., Ochoa, C., Pérez-Lantero, P., Rojas-Ledesma, J.: Matching colored points with rectangles. http://arxiv.org/abs/1309.3696 (2014)

  6. 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

  7. 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)

  8. Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373–392 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  9. Chepoi, V., Felsner, S.: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46(9), 1036–1041 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  10. Cibulka, J., Hladký, J., Kazda, A., Lidický, B., Ondráčková, E., Tancer, M., Jelínek, V.: Personal Communication (2011)

  11. Fon-Der-Flaass, D.G., Kostochka, A.V.: Covering boxes by points. Discrete Math. 120(1), 269–275 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  12. 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)

    Article  MATH  MathSciNet  Google Scholar 

  13. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland, Amsterdam (2004)

    Google Scholar 

  14. Gyárfás, A., Lehel, J.: Covering and coloring problems for relatives of intervals. Discrete Math. 55(2), 167–180 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  15. 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)

  16. Hixon, T.S.: Hook graphs and more: some contributions to geometric graph theory. Masters thesis, Technische Universität Berlin, Berlin (2013)

  17. 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)

    Article  MATH  MathSciNet  Google Scholar 

  18. 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)

    Article  MATH  MathSciNet  Google Scholar 

  19. Károlyi, G.Y.: On point covers of parallel rectangles. Period. Math. Hung. 23(2), 105–107 (1991)

    Article  MATH  Google Scholar 

  20. Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  21. Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  22. Lubiw, A.: A weighted min-max relation for intervals. J. Comb. Theory Ser. B 53(2), 151–172 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  23. Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883–895 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  24. 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)

  25. Soto, M., Thraves, C.: (c-)And graphs—more than intersection, more than geometric. http://arxiv.org/abs/1306.1957 (2013)

  26. Wegner, G.: Über eine kombinatorisch-geometrische frage Hadwiger und Debrunner. Isr. J. Math. 3(4), 187–198 (1965)

  27. Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3(3), 351–358 (1982)

    Article  MATH  MathSciNet  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to José Correa.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-014-9661-y

Keywords

Navigation