Self-approaching paths in simple polygons

DOI10.1016/J.COMGEO.2019.101595MaRDI QIDQ2173458zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Irina Kostitsyna, Stefan Langerman

Publication date 22 April 2020

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.06107

zbMATH Keywords

involute curvesself-approaching pathsshortest pathssimple polygons

Mathematics Subject Classification ID

Inequalities and extremum problems in real or complex geometry (51M16) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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|ge|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 use 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.

Recommendations

• Self-approaching paths in simple polygons
• Self-approaching curves
• An algorithm for computing a convex and simple path of bounded curvature in a simple polygon
• Self-approaching graphs
• Generalized self-approaching curves

Cites work

• Beacon-based algorithms for geometric routing
• Computing common tangents without a separating line
• Curves with increasing chords
• Generalized self-approaching curves
• Geometric algorithms for sensor networks
• scientific article; zbMATH DE number 1256695 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Increasing-chord graphs on point sets
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• Ray shooting in polygons using geodesic triangulations
• Self-approaching curves
• Self-approaching graphs
• Self-approaching paths in simple polygons
• The removal of \pi from some undecidable problems involving elementary functions

Cited in

(5)

• (Weakly) self-approaching geometric graphs and spanners
• Self-approaching paths in simple polygons
• Self-approaching graphs
• On the stretch factor of polygonal chains
• Generalized self-approaching curves

This page was built for publication: Self-approaching paths in simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173458)