Document Open Access Logo

Self-Approaching Paths in Simple Polygons

Authors Prosenjit Bose, Irina Kostitsyna, Stefan Langerman

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2017.21.pdf
  • Filesize: 0.79 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • self-approaching path
  • simple polygon
  • shortest path
  • involute curve

Metrics

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

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.

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

Author Details

Prosenjit Bose
Irina Kostitsyna
Stefan Langerman

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. P. Bose, I. Kostitsyna, and S. Langerman. Self-approaching paths in simple polygons. Preprint, http://arxiv.org/abs/1703.06107, 2017.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
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