CIM Algorithm for Approximating Three Dimensional Polygonal Curves

Junhai Yong Tsinghua University Shi-Min Hu Tsinghua University Jiaguang Sun Tsinghua University

Geometric Modeling and Processing mathscidoc:1609.16002

Journal of Computer Science and Technology, 16, (6), 489-497, 2001.12
The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. In $R^2$, the cone intersection method (CIM) is one of the most eÆcient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) under $L_2$ norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. An approximation algorithm is also presented, which takes $O(n^2)$ time and $O(n)$ space. Results of some examples are given to illustrate the eÆciency of these algorithms.
polygonal curve, CIM, LS-WMN, approximation, optimization
[ Download ] [ 2016-09-17 23:29:21 uploaded by shimin ] [ 509 downloads ] [ 0 comments ] [ Cited by 3 ]
@inproceedings{junhai2001cim,
  title={CIM Algorithm for Approximating Three Dimensional Polygonal Curves},
  author={Junhai Yong, Shi-Min Hu, and Jiaguang Sun},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160917232921055218012},
  booktitle={Journal of Computer Science and Technology},
  volume={16},
  number={6},
  pages={489-497},
  year={2001},
}
Junhai Yong, Shi-Min Hu, and Jiaguang Sun. CIM Algorithm for Approximating Three Dimensional Polygonal Curves. 2001. Vol. 16. In Journal of Computer Science and Technology. pp.489-497. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160917232921055218012.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved