by Li, F and Klette, R
Abstract:
Since the pioneering work by (Cohen and Kimmel, 1997) on finding a contour as a minimal path between two end points, shortest paths in volume images have raised interest in computer vision and image analysis. This paper considers the calculation of a Euclidean shortest path (ESP) in a three-dimensional (3D) polyhedral space Π. We propose an approximate κ(ε)·O(M|V|) 3D ESP algorithm, not counting time for preprocessing. The preprocessing time complexity equals O(M|E|+|F|+|V|log|V|) for solving a special, but ‘fairly general’ case of the 3D ESP problem, where Π does not need to be convex. V and E are the sets of vertices and edges of Π, respectively, and F is the set of faces (triangles) of Π. M is the maximal number of vertices of a so-called critical polygon, and κ(ε) = (L 0 – L)/ε where L 0 is the length of an initial path and L is the true (i.e., optimum) path length. The given algorithm solves approximately three (previously known to be) NP-complete or NP-hard 3D ESP problems in time κ(ε)·O(k), where k is the number of layers in a stack, which is introduced in this paper as being the problem environment. The proposed approximation method has straightforward applications for ESP problems when analyzing polyhedral objects (e.g., in 3D imaging), of for ‘flying’ over a polyhedral terrain. © 2011 Springer-Verlag.
Reference:
Approximate shortest paths in simple polyhedra (Li, F and Klette, R), In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 6607 LNCS, 2011.
Bibtex Entry:
@inproceedings{li2011approximatepolyhedra,
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 = "513--524",
title = "Approximate shortest paths in simple polyhedra",
volume = "6607 LNCS",
year = "2011",
abstract = "Since the pioneering work by (Cohen and Kimmel, 1997) on finding a contour as a minimal path between two end points, shortest paths in volume images have raised interest in computer vision and image analysis. This paper considers the calculation of a Euclidean shortest path (ESP) in a three-dimensional (3D) polyhedral space Π. We propose an approximate κ(ε)·O(M|V|) 3D ESP algorithm, not counting time for preprocessing. The preprocessing time complexity equals O(M|E|+|F|+|V|log|V|) for solving a special, but 'fairly general' case of the 3D ESP problem, where Π does not need to be convex. V and E are the sets of vertices and edges of Π, respectively, and F is the set of faces (triangles) of Π. M is the maximal number of vertices of a so-called critical polygon, and κ(ε) = (L
0 - L)/ε where L
0 is the length of an initial path and L is the true (i.e., optimum) path length. The given algorithm solves approximately three (previously known to be) NP-complete or NP-hard 3D ESP problems in time κ(ε)·O(k), where k is the number of layers in a stack, which is introduced in this paper as being the problem environment. The proposed approximation method has straightforward applications for ESP problems when analyzing polyhedral objects (e.g., in 3D imaging), of for 'flying' over a polyhedral terrain. © 2011 Springer-Verlag.",
doi = "10.1007/978-3-642-19867-0_43",
isbn = "9783642198663",
issn = "0302-9743",
eissn = "1611-3349",
language = "eng",
}