ICS Theory Group

ICS 269, Fall 1996: Theory Seminar

22 Nov 1996:
The Shape of a Set of Points
Nina Amenta, Xerox PARC

Reconstruction of the boundary of an object from an unordered set of points is a fundamental problem in both computer vision and computer graphics, so it would be nice to have a mathematical definition of the ``shape'' of a set of points which reflects the idea that the points lie on a (d - 1)-dimensional surface. We propose a simple definition for points in the plane, called the crust.

We can prove that if a smooth curve is sampled densely enough, then the crust of the samples approximates the curve, with no extraneous features. The minimum required sampling density varies along the curve according to the Local Feature Size (which is also simply defined), so that areas of less detail can be sampled less densely.

The crust is easy to compute using Voronoi diagrams in O(n log n) time (even in practice). We will demonstrate the computation of crusts on arbitrary point sets.