LIPIcs.SoCG.2017.21.pdf
- Filesize: 0.79 MB
- 15 pages
Document
Self-Approaching Paths in Simple Polygons
Authors
-
Part of:
Volume:
33rd International Symposium on Computational Geometry (SoCG 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-06-20
Cite As Get BibTex
Prosenjit Bose, Irina Kostitsyna, and Stefan Langerman. Self-Approaching Paths in Simple Polygons. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.21
Abstract
We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a point moving along the path and any future position does not increase, that is, for all points a, b, and c that appear in that order along the curve, |ac| >= |bc|. We analyze the properties, and present a characterization of shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points inside a polygon can be forced to follow a general class of non-algebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a self-approaching path inside a polygon connecting two points under a model of computation which assumes that we can calculate involute curves of high order. Lastly, we provide an algorithm to test if a given simple polygon is self-approaching, that is, if there exists a self-approaching path for any two points inside the polygon.
Subject Classification
Keywords
- self-approaching path
- simple polygon
- shortest path
- involute curve
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- O. Aichholzer, F. Aurenhammer, C. Icking, R. Klein, E. Langetepe, and G. Rote. Generalized self-approaching curves. Discrete Applied Mathematics, 109(1-2):3-24, 2001. URL: http://dx.doi.org/10.1016/S0166-218X(00)00233-X.
- S. Alamdari, T. M. Chan, E. Grant, A. Lubiw, and V. Pathak. Self-approaching Graphs. In 20th International Symposium on Graph Drawing (GD), pages 260-271, 2012. URL: http://dx.doi.org/10.1007/978-3-642-36763-2_23.
- E. M. Arkin, R. Connelly, and J. S. B. Mitchell. On monotone paths among obstacles with applications to planning assemblies. In 5th Annual Symposium on Computational Geometry (SCG), pages 334-343. ACM Press, 1989. URL: http://dx.doi.org/10.1145/73833.73870.
- M. A. Bender and M. Farach-Colton. The LCA Problem Revisited. In Latin American Symposium on Theoretical Informatics, pages 88-94, 2000. URL: http://dx.doi.org/10.1007/10719839_9.
- M. Biro, J. Iwerks, I. Kostitsyna, and J. S. B. Mitchell. Beacon-Based Algorithms for Geometric Routing. In 13th Algorithms and Data Structures Symposium (WADS), pages 158-169. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40104-6_14.
- P. Bose, I. Kostitsyna, and S. Langerman. Self-approaching paths in simple polygons. Preprint, http://arxiv.org/abs/1703.06107, 2017.
- B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1):54-68, 1994. URL: http://dx.doi.org/10.1007/BF01377183.
- H. Dehkordi, F. Frati, and J. Gudmundsson. Increasing-Chord Graphs On Point Sets. In 22nd International Symposium on Graph Drawing, pages 464-475. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45803-7_39.
- L. E. Dubins. On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents. American Journal of Mathematics, 79(3):497-516, 1957. URL: http://dx.doi.org/10.2307/2372560.
- J. Gao and L. Guibas. Geometric algorithms for sensor networks. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 370(1958):27-51, 2012. URL: http://dx.doi.org/10.1098/rsta.2011.0215.
- L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209-233, 1987. URL: http://dx.doi.org/10.1007/BF01840360.
- C. Icking and R. Klein. Searching for the kernel of a polygon - a competitive strategy. In 11th Annual Symposium on Computational Geometry (SCG), pages 258-266. ACM Press, 1995. URL: http://dx.doi.org/10.1145/220279.220307.
- C. Icking, R. Klein, and E. Langetepe. Self-approaching curves. Mathematical Proceedings of the Cambridge Philosophical Society, 125(3):441-453, 1999. URL: http://dx.doi.org/10.1017/S0305004198003016.
- M. Laczkovich. The removal of π from some undecidable problems involving elementary functions. Proceedings of the American Mathematical Society, 131(07):2235-2241, 2003. URL: http://dx.doi.org/10.1090/S0002-9939-02-06753-9.
- J. S. B. Mitchell, C. Piatko, and E. M. Arkin. Computing a shortest k-link path in a polygon. In 33rd Annual Symposium on Foundations of Computer Science, pages 573-582. IEEE, 1992. URL: http://dx.doi.org/10.1109/SFCS.1992.267794.
- M. Nöllenburg, R. Prutkin, and I. Rutter. On self-approaching and increasing-chord drawings of 3-connected planar graphs. Journal of Computational Geometry, 7(1):47-69, 2016. URL: http://dx.doi.org/10.20382/jocg.v7i1a3.
- G. Rote. Curves with increasing chords. Mathematical Proceedings of the Cambridge Philosophical Society, 115(01):1, 1994. URL: http://dx.doi.org/10.1017/S0305004100071875.