Two Approximative Algorithms for Calculating Minimum-Length Polygons in 3D Space
Fajie Li, Reinhard Klette · 2005
We consider simple cube-curves in the orthogonal 3D grid. The union of all cells contained in such a curve (also called the tube of this curve) is a polyhedrally bounded set. The curve’s length is defined to be that of the minimum-length polygonal curve (MLP) fully contained and complete in the tube of the curve. So far no provable general algorithm is known for the approximative calculation of such an MLP. This paper presents two approximative algorithms for computing the MLP of a general simple cube-curve in O(n 4) time, where n is the total number of critical edges of the given simple cube-curve.