On the shape of a set of points in the plane

article On the shape of a set of points in the plane published yes Herbert Edelsbrunner author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833 David Kirkpatrick author Raimund Seidel author 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. IEEE1983 eng IEEE Transactions on Information Theory 0018-9162 1558-081410.1109/TIT.1983.1056714 294551 - 559 yes 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. IEEE. <a href="https://doi.org/10.1109/TIT.1983.1056714 ">https://doi.org/10.1109/TIT.1983.1056714 </a> 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:<a href="https://doi.org/10.1109/TIT.1983.1056714 ">10.1109/TIT.1983.1056714 </a>. 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 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:<a href="https://doi.org/10.1109/TIT.1983.1056714 ">10.1109/TIT.1983.1056714 </a> H. Edelsbrunner, D. Kirkpatrick, R. Seidel, IEEE Transactions on Information Theory 29 (1983) 551–559. 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. <a href="https://doi.org/10.1109/TIT.1983.1056714 ">https://doi.org/10.1109/TIT.1983.1056714 </a>. 41282018-12-11T12:07:06Z2022-01-25T12:55:07Z