Self-approaching paths in simple polygons

P. Bose, I. Kostitsyna, S. Langerman

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
43 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 33rd International Symposium on Computational Geometry (SoCG)
EditorsMatthew J. Katz, Boris Aronov
Number of pages15
ISBN (Electronic)9783959770385
DOIs
Publication statusPublished - 2017
Event33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017
Conference number: 33
http://socg2017.smp.uq.edu.au/socg.html
http://socg2017.smp.uq.edu.au/index.html

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume77
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Computational Geometry (SoCG 2017)
Abbreviated titleSoCG 2017
CountryAustralia
CityBrisbane
Period4/07/177/07/17
OtherThe Computational Geometry Week (CG Week 2017) is the premier international forum for advances in computational geometry and its many applications. The next edition will take place in Brisbane, Australia, July 4-7, 2017.
CG week combines a number of events, most notably the 33rd International Symposium on Computational Geometry (SoCG 2017), the associated multimedia exposition, workshops, and the Young Researchers Forum.
Internet address

Keywords

  • Involute curve
  • Self-approaching path
  • Shortest path
  • Simple polygon

Cite this