Approximating a neuron with cylindrical segments
Wenhao Lin · Montana State University ScholarWorks (Montana State University) · 2003
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 and lengths) enclosing S such that the sum of their radii is minimized.There is no known result in this direction except when K = 1.When K is not part of the inputs, this problem is strongly NP-hard.In this thesis, we present new approximation algorithms for K = 1.We attack the general problem by taking input as a reconstructed 3D polyhedron from the sample points from practice.We apply a semi-automatic method to divide one polyhedron into K parts, so that we can apply our approximation algorithms on each part.At last, we present the design of one software system using these ideas.