On the shape of a set of points in the plane

H. Edelsbrunner, D. Kirkpatrick, R. Seidel, IEEE Transactions on Information Theory 29 (1983) 551–559.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
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.
Publishing Year
Date Published
1983-01-01
Journal Title
IEEE Transactions on Information Theory
Volume
29
Issue
4
Page
551 - 559
IST-REx-ID

Cite this

Edelsbrunner H, Kirkpatrick D, Seidel R. On the shape of a set of points in the plane. IEEE Transactions on Information Theory. 1983;29(4):551-559. doi:10.1109/TIT.1983.1056714
Edelsbrunner, H., Kirkpatrick, D., & Seidel, R. (1983). On the shape of a set of points in the plane. IEEE Transactions on Information Theory, 29(4), 551–559. https://doi.org/10.1109/TIT.1983.1056714
Edelsbrunner, Herbert, David Kirkpatrick, and Raimund Seidel. “On the Shape of a Set of Points in the Plane.” IEEE Transactions on Information Theory 29, no. 4 (1983): 551–59. https://doi.org/10.1109/TIT.1983.1056714 .
H. Edelsbrunner, D. Kirkpatrick, and R. Seidel, “On the shape of a set of points in the plane,” IEEE Transactions on Information Theory, vol. 29, no. 4, pp. 551–559, 1983.
Edelsbrunner H, Kirkpatrick D, Seidel R. 1983. On the shape of a set of points in the plane. IEEE Transactions on Information Theory. 29(4), 551–559.
Edelsbrunner, Herbert, et al. “On the Shape of a Set of Points in the Plane.” IEEE Transactions on Information Theory, vol. 29, no. 4, IEEE, 1983, pp. 551–59, doi:10.1109/TIT.1983.1056714 .

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar