Advanced Search
Sun Chunjuan, Zhu Binhai, Wang Wencheng. Optimizing Conical Reconstruction of Linear Point Clouds[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(8): 1324-1330.
Citation: Sun Chunjuan, Zhu Binhai, Wang Wencheng. Optimizing Conical Reconstruction of Linear Point Clouds[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(8): 1324-1330.

Optimizing Conical Reconstruction of Linear Point Clouds

  • Finding the smallest conical objects (namely cylindrical segments, cones and cone frustums) to enclose a set of linear 3D points is a strong NP-hard problem. In this paper, an approximate algorithm to this NP-problem is presented. The algorithm adaptively divides the set of n points into subsets, and then approximates every subset by a conical object respectively. The algorithm is optimized in the sense that the volume of the approximated conical object is guaranteed to bound at most (1+ε) times of the actual volume of the point set. The time complexity of the algorithm for producing an approximated cone is O (n/ε3), which improves the time bound in existing methods, where ε is a preset threshold for approximation. Experimental results show that the algorithm is fast and effective.
  • loading

Catalog

    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return