Abstract: 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/ε³), 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.