by Li, F, Klette, R and Fu, X
Abstract:
Let p and q be two points on the surface of a polytope ∏. This paper provides a rubberband algorithm for computing a Euclidean shortest path between p and q (a so-called surface ESP) that is contained on the surface of ∏. The algorithm has κ1(ε) ·κ2(ε )· Script O Sign (n2) time complexity, where n is the number of vertices of ∏, κ1(ε) = (L0i-L i)/ε, for the true length Li of some shortest path with initial (polygonal path) length L0i (used when approximating this shortest path), for i = 1, 2. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithm is easy to implement and thus of importance for applications, for example, when analyzing 3D objects in 3D image analysis, such as in biomedical or industrial image analysis, using 3D image scanners. © Springer-Verlag Berlin Heidelberg 2007.
Reference:
Approximate ESPs on surfaces of polytopes using a rubberband algorithm (Li, F, Klette, R and Fu, X), In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 4872 LNCS, 2007.
Bibtex Entry:
@inproceedings{li2007approximatealgorithm,
author = "Li, F and Klette, R and Fu, X",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "236--247",
title = "Approximate ESPs on surfaces of polytopes using a rubberband algorithm",
volume = "4872 LNCS",
year = "2007",
abstract = "Let p and q be two points on the surface of a polytope ∏. This paper provides a rubberband algorithm for computing a Euclidean shortest path between p and q (a so-called surface ESP) that is contained on the surface of ∏. The algorithm has κ1(ε) ·κ2(ε )· Script O Sign (n2) time complexity, where n is the number of vertices of ∏, κ1(ε) = (L0i-L i)/ε, for the true length Li of some shortest path with initial (polygonal path) length L0i (used when approximating this shortest path), for i = 1, 2. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithm is easy to implement and thus of importance for applications, for example, when analyzing 3D objects in 3D image analysis, such as in biomedical or industrial image analysis, using 3D image scanners. © Springer-Verlag Berlin Heidelberg 2007.",
isbn = "9783540771289",
issn = "0302-9743",
eissn = "1611-3349",
keyword = "Euclidean shortest path",
keyword = "Rubberband algorithm",
keyword = "Surface ESP",
language = "eng",
}