Technical Reports

The ICICS/CS Reading Room

UBC CS TR-81-15 Summary

On the Shape of a Set of Points in the Plane, September 1981 H. Edelsbrunner, David G. Kirkpatrick and Raimund Seidel

A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, called ``shapes'', which seem to capture the intuitive notion of ``fine shape'' and ``crude shape'' of point sets. .br Additionally, close relationships with Delaunay triangulations are revealed and, relying on these results, an optimal algorithm that constructs ``shapes'' is developed.

If you have any questions or comments regarding this page please send mail to