Shape and medial axis approximation from samples

Samples of objects, which essentially carry the shape information of the objects, play a more and more important role in many applications. Shape approximation and medial axis approximation from these samples are two key problems that need to be addressed for geometric modeling with point samples. In this dissertation, we present the algorithms for these problems along with their theoretical guarantees.; The shape approximation problem considered in this work is the generalization of the curve and surface reconstruction which have the limitation that the dimension of the sampled objects has to be known a priori. We propose a Voronoi-based two-stage algorithm which solves this problem. At the first stage, the dimension of the sample points which is defined as the dimension of the manifolds they belong to is detected. The theoretical guarantee comes with the assumption that the sample has to be reasonably dense and the sampled objects have to be smooth manifolds without boundaries. But in practice, it works well for datasets which do not satisfy these conditions.; Based on the dimension information of a sample, we design a shape approximation algorithm which approximates the sampled manifolds with a piecewise linear complex interpolating the sample. In three dimensions, we extract manifolds from the approximate complex.; Medial axis provides an alternative representation of shapes which has advantages over other representations in many applications. Exact computation of the medial axis is difficult in general and an approximation is more useful in many cases. In this work, we develop a Voronoi-based algorithm to approximate the medial axis of 3D objects from their samples. Our algorithm is the first such an algorithm with a convergence guarantee and it has the feature that it is independent of scale and density.; Obviously, the approximation quality of our medial axis algorithm is limited by the input sample. In some cases such as CAD objects, the surface from which the samples are derived is known. We improve the approximation by incorporating this information into our medial axis approximation algorithm. The quality of the approximation achieved by the modified algorithm is quite good.