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, [Formula presented]. 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.

Additional Metadata | |
---|---|

Involute curves, Self-approaching paths, Shortest paths, Simple polygons | |

dx.doi.org/10.1016/j.comgeo.2019.101595 | |

Computational Geometry | |

Organisation | School of Computer Science |

Bose, P, Kostitsyna, I. (Irina), & Langerman, S. (Stefan). (2020). Self-approaching paths in simple polygons.
Computational Geometry. doi:10.1016/j.comgeo.2019.101595 |