Minimum-length polygons of first-class simple cube-curves


by Li, F and Klette, R
Abstract:
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 only one general algorithm called rubber-band algorithm was known for the approximative calculation of such an MLP. A proof that this algorithm always converges to the correct curve, is still an open problem. This paper proves that the rubber-band algorithm is correct for the family of first-class simple cube-curves. © Springer-Verlag Berlin Heidelberg 2005.
Reference:
Minimum-length polygons of first-class simple cube-curves (Li, F and Klette, R), In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 3691 LNCS, 2005.
Bibtex Entry:
@inproceedings{li2005minimum-lengthcube-curves,
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 = "321--329",
title = "Minimum-length polygons of first-class simple cube-curves",
volume = "3691 LNCS",
year = "2005",
abstract = "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 only one general algorithm called rubber-band algorithm was known for the approximative calculation of such an MLP. A proof that this algorithm always converges to the correct curve, is still an open problem. This paper proves that the rubber-band algorithm is correct for the family of first-class simple cube-curves. © Springer-Verlag Berlin Heidelberg 2005.",
isbn = "3540289690",
isbn = "9783540289692",
issn = "0302-9743",
eissn = "1611-3349",
language = "eng",
}