On the shape of a set of points in the plane
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.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Kirkpatrick, David;
Seidel, Raimund
;
Kirkpatrick, David;
Seidel, RaimundAbstract
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 optimal O(n \log n) algorithm that constructs \alpha -shapes is developed.
Publishing Year
Date Published
1983-06-01
Journal Title
IEEE Transactions on Information Theory
Acknowledgement
The authors express their appreciation for numerous constructive suggestions, which led to improvements on
various phases of the manuscript, to Dr. Marvin Simon of JPL and to Professor George L. Turin of University of
California, Berkeley. The junior author also gratefully acknowledges the role of the latter as her M.S. research
advisor on the project which formed the nucleus of this work.
Volume
29
Issue
4
Page
551 - 559
ISSN
eISSN
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. IEEE. 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. IEEE, 1983. 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. IEEE, 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 .
Google Scholar