Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.21
URN: urn:nbn:de:0030-drops-72166
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7216/
Bose, Prosenjit ; Kostitsyna, Irina ; Langerman, Stefan
Self-Approaching Paths in Simple Polygons
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{bose_et_al:LIPIcs:2017:7216,
author = {Prosenjit Bose and Irina Kostitsyna and Stefan Langerman},
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 = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7216},
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}
}
| Keywords: | self-approaching path, simple polygon, shortest path, involute curve | |
| Seminar: | 33rd International Symposium on Computational Geometry (SoCG 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 20.06.2017 |
