Document Open Access Logo

Convex Partial Transversals of Planar Regions

Authors Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, Lionov Wiratma

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2018.52.pdf
  • Filesize: 0.64 MB
  • 12 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • computational geometry
  • algorithms
  • NP-hardness
  • convex transversals

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

Cite As Get BibTex

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.52

Author Details

Vahideh Keikha
  • Dept. of Mathematics and Computer Science, University of Sistan and Baluchestan, Zahedan, Iran
Mees van de Kerkhof
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Marc van Kreveld
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Irina Kostitsyna
  • Dept. of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands
Maarten Löffler
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Frank Staals
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Jérôme Urhausen
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Jordi L. Vermeulen
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Lionov Wiratma
  • Dept. of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, Dept. of Informatics, Parahyangan Catholic University, Bandung, Indonesia

Funding

  • van de Kerkhof, Mees: M.v.d.K. supported by the Netherlands Organisation for Scientific Research under proj. 628.011.005.
  • van Kreveld, Marc: M.v.K. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651.
  • Löffler, Maarten: M.L. supported by the Netherlands Organisation for Scientific Research under proj. 614.001.504.
  • Staals, Frank: F.S. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651.
  • Urhausen, Jérôme: J.U. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651.
  • Vermeulen, Jordi L.: J.V. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651.
  • Wiratma, Lionov: L.W. supported by the Mnst. of Research, Techn. and High. Ed. of Indonesia (No. 138.41/E4.4/2015).

References

  1. E. M. Arkin, A. Banik, P. Carmi, G. Citovsky, M. J. Katz, J. S. B. Mitchell, and M. Simakov. Conflict-free Covering. In Proc. 27th Canadian Conference on Computational Geometry (CCCG), pages 17-23, 2015. Google Scholar
  2. E. M. Arkin, C. Dieckmann, C. Knauer, J. S. B. Mitchell, V. Polishchuk, L. Schlipf, and S. Yang. Convex transversals. Computational Geometry, 47(2, Part B):224-239, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2012.10.009.
  3. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 3rd edition, 2008. Google Scholar
  4. D. Eppstein, M. Overmars, G. Rote, and G. Woeginger. Finding Minimum Area k-gons. Discrete &Computational Geometry, 7(1):45-58, 1992. URL: http://dx.doi.org/10.1007/BF02187823.
  5. G. Even, Z. Lotker, D. Ron, and S. Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing, 33(1):94-136, 2003. Google Scholar
  6. M. T. Goodrich and J. S. Snoeyink. Stabbing parallel segments with a convex polygon. Computer Vision, Graphics, and Image Processing, 49(2):152-170, 1990. Google Scholar
  7. S. Har-Peled and S. Smorodinsky. Conflict-free coloring of points and simple regions in the plane. Discrete &Computational Geometry, 34(1):47-70, 2005. Google Scholar
  8. M. J. Katz, N. Lev-Tov, and G. Morgenstern. Conflict-free coloring of points on a line with respect to a set of intervals. Computational Geometry, 45(9):508-514, 2012. Google Scholar
  9. V. Keikha, M. van de Kerkhof, M. van Kreveld, I. Kostitsyna, M. Löffler, F. Staals, J. Urhausen, J. L. Vermeulen, and L. Wiratma. Convex partial transversals of planar regions. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.10078.
  10. J. S. B. Mitchell, G. Rote, G. Sundaram, and G. Woeginger. Counting convex polygons in planar point sets. Information Processing Letters, 56(1):45-49, 1995. URL: http://dx.doi.org/10.1016/0020-0190(95)00130-5.
  11. M. H. Overmars and E. Welzl. New Methods for Computing Visibility Graphs. In Proc. 4th Annual Symposium on Computational Geometry (SCG), pages 164-171, 1988. URL: http://dx.doi.org/10.1145/73393.73410.
  12. G. Rote, G. Woeginger, B. Zhu, and Z. Wang. Counting k-subsets and convex k-gons in the plane. Information Processing Letters, 38(3):149-151, 1991. Google Scholar
  13. L. Schlipf. Notes on Convex Transversals. arXiv preprint, 2012. URL: http://arxiv.org/abs/1211.5107.
  14. M. Tompa. An optimal solution to a wire-routing problem. Journal of Computer and System Sciences, 23(2):127-150, 1981. URL: http://dx.doi.org/10.1016/0022-0000(81)90010-6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact