Analysis of the Rubberband Algorithm

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Li, Fajie en
dc.contributor.author Klette, Reinhard en
dc.date.accessioned 2008-08-21T01:57:00Z en
dc.date.available 2008-08-21T01:57:00Z en
dc.date.issued 2006 en
dc.identifier.citation Communication and Information Technology Research Technical Report 175, (2006) en
dc.identifier.issn 1178-3570 en
dc.identifier.uri http://hdl.handle.net/2292/2795 en
dc.description You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). en
dc.description.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) contained and complete in the tube of the curve. Only one general algorithm, called rubberband algorithm, was known for the approximative calculation of such an MLP so far. An open problem in KLE_ROS_2004 is related to the design of algorithms for the calculation of the MLP of a simple cube-curve: Is there a simple cube-curve such that none of the nodes of its MLP is a grid vertex? This paper constructs an example of such a simple cube-curve, and we also characterize the class of all of such cube-curves. This study leads to a correction in Option 3 of the rubberband algorithm (by adding one missing test). We also prove that the rubber-band algorithm has linear time complexity ${\cal O}(m)$ where $m$ is the number of critical edges of a given simple cube curve, which solves another open problem in the context of this algorithm. en
dc.publisher CITR, The University of Auckland, New Zealand en
dc.relation.ispartofseries Communication and Information Technology Research (CITR) Technical Report Series en
dc.rights Copyright CITR, The University of Auckland. You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site under terms that include this permission. All other rights are reserved by the author(s). en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri http://citr.auckland.ac.nz/techreports/2006/CITR-TR-175.pdf en
dc.title Analysis of the Rubberband Algorithm en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en


Full text options

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Advanced Search

Browse