An Approach to the Solving Non-Steiner Minimum Link Path Problem

Authors: V. Tereshchenko, A. Tregubenko

Abstract:

In this study we survey the method for fast finding a minimum link path between two arbitrary points within a simple polygon, which can pass only through the vertices, with preprocessing.

Keywords: Minimum link path, simple polygon, Steiner points, optimal algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329372

References:

[2] E.M. Arkin, J.S.B. Mitchell, and S.Suri. Optimal link path queries in a simple polygon. In Proc.3rd ACM-SIAM Sympos. Discrete Algorithms, 1992, p:269-279.
[3] W. McAveney. Minimum link path finding methods in 2D polygons. CS 633 Fall 2007.
[4] J. Hershberger. An optimal visibility graph algorithm for triangulated simple polygons. Algorithmica, 4,1989 p:141-155.
[5] B. Joe and R.B. Simpson. Correction to Lee-s visibility polygon algorithm. BIT, 27, 1987, p:458-473.
[6] A Goldberg. P-to-P shortest path algorithms with preprocessing. Sofsem, 2007.
[7] D.T. Lee. On finding the convex hull of a simple polygon. IJCIS, Vol.12, No. 2, 1983, pages 87-98.
[8] M. Nouri, M.Ghodsi. Space-query-time tradeoff for computing the visibility polygon. LNCS, Vol.5598, 2009, pages 120-131.