Approximating 3D points with cylindrical segments

作者：Zhu BH^*

来源：International Journal of Computational Geometry and Applications, 2004, 14(3): 189-201.

DOI：10.1142/S0218195904001421

• biological modeling
• neural maps
• approximation algorithms
• NP-hardness

In this paper, we study a 3D geometric problem originated from computing neural maps in the computational biology community: Given a set S of n points in 3D, compute k cylindrical segments (with different radii, orientations, lengths and no segment penetrates another) enclosing S such that the sum of their radii is minimized. There is no known result in this direction except when k = 1. The general problem is strongly NP-hard and we obtain a polynomial time approximation scheme (PTAS) for any fixed k > 1 in O(n(3k-2)/delta(4k-3)) time by returning k cylindrical segments with sum of radii at most (1 + delta) of the corresponding optimal value, if exist. Our PTAS is built upon a simple (though slower) approximation algorithm for the case when k = 1.

• 出版日期2004-6