Self-approaching paths in simple polygons

P. Bose, I. Kostitsyna, S. Langerman

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)
43 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings of the 33rd International Symposium on Computational Geometry (SoCG)
RedacteurenMatthew J. Katz, Boris Aronov
Aantal pagina's15
ISBN van elektronische versie9783959770385
DOI's
StatusGepubliceerd - 2017
Evenement33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australië
Duur: 4 jul 20177 jul 2017
Congresnummer: 33
http://socg2017.smp.uq.edu.au/socg.html
http://socg2017.smp.uq.edu.au/index.html

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume77
ISSN van geprinte versie1868-8969

Congres

Congres33rd International Symposium on Computational Geometry (SoCG 2017)
Verkorte titelSoCG 2017
LandAustralië
StadBrisbane
Periode4/07/177/07/17
Internet adres

Citeer dit