Digital curves in 3D space and a linear-time length estimation algorithm

Author

Bülow, Thomas ; Klette, Reinhard

Author_Institution

Comput. Sci. Div., California Univ., Berkeley, CA, USA

Volume

24

Issue

7

fYear

2002

fDate

7/1/2002 12:00:00 AM

Firstpage

962

Lastpage

970

Abstract

We consider simple digital curves in a 3D orthogonal grid as special polyhedrally bounded sets. These digital curves model digitized curves or arcs in three-dimensional Euclidean space. The length of such a simple digital curve is defined to be the length of the minimum-length polygonal curve fully contained and complete in the tube of this digital curve. So far, no algorithm was known for the calculation of such a shortest polygonal curve. The paper provides an iterative algorithmic solution for approximating the minimum-length polygon of a given simple digital space-curve. The theoretical foundations of this algorithm are presented as well as experimental results

Keywords

computational complexity; computational geometry; iterative methods; set theory; 3D orthogonal grid; 3D space; cellular complexes; digital curves; digital geometry; digital space-curve; iterative algorithmic solution; linear-time length estimation algorithm; minimum-length polygonal curve; polyhedrally bounded sets; shortest polygonal curve; Data analysis; Geometry; Helium; Image analysis; Iterative algorithms; Optimization methods; Shortest path problem; Skeleton; Solids; Time measurement;

fLanguage

English

Journal_Title

Pattern Analysis and Machine Intelligence, IEEE Transactions on

Publisher

ieee

ISSN

0162-8828

Type

jour

DOI

10.1109/TPAMI.2002.1017622

Filename

1017622