Bose, Prosenjit ;
Kostitsyna, Irina ;
Langerman, Stefan
SelfApproaching Paths in Simple Polygons
Abstract
We study selfapproaching paths that are contained in a simple polygon. A selfapproaching 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 selfapproaching paths. In particular, we show that a shortest selfapproaching path connecting two points inside a polygon can be forced to follow a general class of nonalgebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a selfapproaching 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 selfapproaching, that is, if there exists a selfapproaching 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 = {{SelfApproaching Paths in Simple Polygons}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7216},
URN = {urn:nbn:de:0030drops72166},
doi = {10.4230/LIPIcs.SoCG.2017.21},
annote = {Keywords: selfapproaching path, simple polygon, shortest path, involute curve}
}
20.06.2017
Keywords: 

selfapproaching 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 