LIPIcs.ISAAC.2018.52.pdf
- Filesize: 0.64 MB
- 12 pages
Document
Convex Partial Transversals of Planar Regions
Authors
-
Part of:
Volume:
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-06
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.ISAAC.2018.52
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.
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)
0PDF Downloads
References
-
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.
- 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.
-
M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 3rd edition, 2008.
- 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.
-
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.
-
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.
-
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.
-
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.
- 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.
- 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.
- 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.
-
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.
- L. Schlipf. Notes on Convex Transversals. arXiv preprint, 2012. URL: http://arxiv.org/abs/1211.5107.
- 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.