by Li, F and Klette, R

Abstract:

We consider simple cube-curves in the orthogonal 3D grid of cells. 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 a MLP. There is an open problem which is related to the design of algorithms for calculation a 3D MLP of a cube-curve: Is there a simple cube-curve such that none of the vertices of its 3D MLP is a grid vertex? This paper constructs an example of such a simple cube-curve. We also characterize this class of cube-curves. © Springer-Verlag Berlin Heidelberg 2005.

Reference:

The class of simple cube-curves whose MLPs cannot have vertices at grid points (Li, F and Klette, R), In Lecture Notes in Computer Science, volume 3429, 2005.

Bibtex Entry:

@inproceedings{li2005thepoints, author = "Li, F and Klette, R", booktitle = "Lecture Notes in Computer Science", pages = "183--194", title = "The class of simple cube-curves whose MLPs cannot have vertices at grid points", volume = "3429", year = "2005", abstract = "We consider simple cube-curves in the orthogonal 3D grid of cells. 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 a MLP. There is an open problem which is related to the design of algorithms for calculation a 3D MLP of a cube-curve: Is there a simple cube-curve such that none of the vertices of its 3D MLP is a grid vertex? This paper constructs an example of such a simple cube-curve. We also characterize this class of cube-curves. © Springer-Verlag Berlin Heidelberg 2005.", issn = "0302-9743", language = "eng", }