On the shape of a set of points in the plane
Herbert Edelsbrunner
Kirkpatrick, David G
Seidel, Raimund
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.
IEEE
1983
info:eu-repo/semantics/article
doc-type:article
text
https://research-explorer.app.ist.ac.at/record/4128
Edelsbrunner H, Kirkpatrick D, Seidel R. On the shape of a set of points in the plane. <i>IEEE Transactions on Information Theory</i>. 1983;29(4):551-559. doi:<a href="https://doi.org/10.1109/TIT.1983.1056714 ">10.1109/TIT.1983.1056714 </a>
info:eu-repo/semantics/altIdentifier/doi/10.1109/TIT.1983.1056714
info:eu-repo/semantics/closedAccess