Self-approaching paths in simple polygons

Prosenjit Bose, Irina Kostitsyna (Corresponding author), Stefan Langerman

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
168 Downloads (Pure)

Abstract

We study the problem of connecting two points in a simple polygon with a self-approaching path. A self-approaching path is a directed curve 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 properties of self-approaching paths inside simple polygons, and characterize shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points in a simple 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 the shortest self-approaching path under a model of computation which assumes that we can compute involute curves of high order. Lastly, we provide an efficient 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.

Original languageEnglish
Article number101595
Number of pages24
JournalComputational Geometry
Volume87
DOIs
Publication statusPublished - Apr 2020

Funding

This work was begun at the CMO-BIRS Workshop on Searching and Routing in Discrete and Continuous Domains, October 11–16, 2015. I.K. was supported in part by the NWO under project no. 612.001.106 , and by F.R.S.-FNRS .

FundersFunder number
Fonds De La Recherche Scientifique - FNRS
Nederlandse Organisatie voor Wetenschappelijk Onderzoek612.001.106

    Keywords

    • Involute curves
    • Self-approaching paths
    • Shortest paths
    • Simple polygons

    Fingerprint

    Dive into the research topics of 'Self-approaching paths in simple polygons'. Together they form a unique fingerprint.

    Cite this