Search

The medial axis of a shape is known to carry a lot of information about the shape. In particular, a recent result of Lieutier establishes that every bounded open subset of ℝn has the same homotopy type as its medial axis. In this paper we provide an algorithm that computes a structure we call the core for the approximation of the medial axis of a shape with smooth boundary from a discrete sample of its boundary. The core is a piecewise linear cell complex that is guaranteed to capture the topology of the medial axis of the shape provided the sample of its boundary is sufficiently dense but not necessarily uniform. We also present a natural method for augmenting the core in order to extend it geometrically while maintaining the topological guarantees. The definition of the core and its extension are based on the steepest ascent flow map that results from the distance function induced by the sample point set. We also provide a geometric guarantee on the closeness of the core and the actual medial axis. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem arising in many practical applications. In this paper, we present new geometric approximation and exact algorithms for the density-based data clustering problem in d-dimensional space ℝd (for any constant integer d ≥ 2). Previously known algorithms for this problem are efficient only when the specified range around each input point, called the δ-neighborhood, contains on average a constant number of input points. Different distributions of the input data points have significant impact on the efficiency of these algorithms. In the worst case when the data points are highly clustered, these algorithms run in quadratic time, although such situations might not occur very frequently on real data. By using computational geometry techniques, we develop faster approximation and exact algorithms for the density-based data clustering problem in ℝd. In particular, our approximation algorithm based on the ∊-fuzzy distance function takes O(n log n) time for any given fixed value ∊>0, and our exact algorithms take sub-quadratic time. The running times and output quality of our algorithms do not depend on any particular data distribution. We believe that our fast approximation algorithm is of considerable practical importance, while our sub-quadratic exact algorithms are more of theoretical interest. We implemented our approximation algorithm and the experimental results show that our approximation algorithm is efficient on arbitrary input point sets. [ABSTRACT FROM AUTHOR]

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(n3k-2/δ4k-3) time by returning k cylindrical segments with sum of radii at most (1+δ) of the corresponding optimal value, if exist. Our PTAS is built upon a simple (though slower) approximation algorithm for the case when k=1. [ABSTRACT FROM AUTHOR]

Determining the best shape to fit a set of points is a fundamental problem in many areas of computer science. We present an algorithm to approximate the k-flat that best fits a set of n points with n - m outliers. This problem generalizes the smallest m-enclosing ball, infinite cylinder, and slab. Our algorithm gives an arbitrary constant factor approximation in O(nk+2/m) time, regardless of the dimension of the point set. While our upper bound nearly matches the lower bound, the algorithm may not be feasible for large values of k. Fortunately, for some practical sets of inliers, we reduce the running time to O(nk+2/mk+1), which is linear when m = Ω(n). [ABSTRACT FROM AUTHOR]