by Li, F and Klette, R
Abstract:
Let p and q be two points in a simple polygon Π. An open problem in computational geometry asks to devise a simple linear-time algorithm for computing a shortest path between p and q, which is contained in Π, such that the algorithm does not depend on a (complicated) linear-time triangulation algorithm. This report provides a contribution to the solution of this problem by applying the rubberband algorithm. The obtained solution has log n) time complexity (where the super-linear time complexity is only due to preprocessing, i.e. for the calculation of critical edges) and is, altogether, considerably simpler than the triangulation algorithm. It has applications in 2D pattern recognition, picture analysis, robotics, and so forth. © 2006 Springer-Verlag.
Reference:
Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm (Li, F and Klette, R), In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 4319 LNCS, 2006.
Bibtex Entry:
@inproceedings{li2006findingalgorithm,
author = "Li, F and Klette, R",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "280--291",
title = "Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm",
volume = "4319 LNCS",
year = "2006",
abstract = "Let p and q be two points in a simple polygon Π. An open problem in computational geometry asks to devise a simple linear-time algorithm for computing a shortest path between p and q, which is contained in Π, such that the algorithm does not depend on a (complicated) linear-time triangulation algorithm. This report provides a contribution to the solution of this problem by applying the rubberband algorithm. The obtained solution has log n) time complexity (where the super-linear time complexity is only due to preprocessing, i.e. for the calculation of critical edges) and is, altogether, considerably simpler than the triangulation algorithm. It has applications in 2D pattern recognition, picture analysis, robotics, and so forth. © 2006 Springer-Verlag.",
doi = "10.1007/11949534-28",
isbn = "354068297X",
isbn = "9783540682974",
issn = "0302-9743",
eissn = "1611-3349",
keyword = "Computational geometry",
keyword = "Digital geometry",
keyword = "Euclidean shortest path",
keyword = "Rubberband algorithm",
keyword = "Simple polygon",
language = "eng",
}