TY - JOUR
AB - 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, "alpha-shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimalO(n log n)algorithm that constructsalpha-shapes is developed.
AU - Herbert Edelsbrunner
AU - Kirkpatrick, David G
AU - Seidel, Raimund
ID - 4128
IS - 4
JF - IEEE Transactions on Information Theory
TI - On the shape of a set of points in the plane
VL - 29
ER -