10.1109/TIT.1983.1056714
Herbert Edelsbrunner
Herbert
Edelsbrunner0000-0002-9823-6833
Kirkpatrick, David G
David
Kirkpatrick
Seidel, Raimund
Raimund
Seidel
On the shape of a set of points in the plane
IEEE
1983
2018-12-11T12:07:06Z
2019-04-26T07:22:41Z
journal_article
https://research-explorer.app.ist.ac.at/record/4128
https://research-explorer.app.ist.ac.at/record/4128.json
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.