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.
@InProceedings{bose_et_al:LIPIcs.SoCG.2017.21, author = {Bose, Prosenjit and Kostitsyna, Irina and Langerman, Stefan}, title = {{Self-Approaching Paths in Simple Polygons}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {21:1--21:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.21}, URN = {urn:nbn:de:0030-drops-72166}, doi = {10.4230/LIPIcs.SoCG.2017.21}, annote = {Keywords: self-approaching path, simple polygon, shortest path, involute curve} }
Feedback for Dagstuhl Publishing