文章基本信息

标题：Self-Approaching Paths in Simple Polygons
本地全文：下载
作者：Prosenjit Bose ; Irina Kostitsyna ; Stefan Langerman 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：21:1-21:15
DOI：10.4230/LIPIcs.SoCG.2017.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：self-approaching path; simple polygon; shortest path; involute curve