# 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.