CITR-TR-55 December 1999
Digital Curves in 3D Sapce and a Linear-Time Length Estimation Algorithm
Thomas Bülow1, and Reinhard Klette1

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 euclidian 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. This paper provides an iterative algorithmic solution, including a presentation of its foundations and of experimental results.

(Adobe PDF / 279K)

  1. Institute of Computer Science, Christian Albrechts University, Preusserstrasse 1-9, 24105 Kiel, Germany
  2. CITR, Tamaki Campus, University of Auckland, Private Bag 92019, Auckland, New Zealand