---
_id: '4128'
abstract:
- lang: eng
  text: 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.
acknowledgement: "The authors express their appreciation for numerous constructive
  suggestions, which led to improvements on\r\nvarious phases of the manuscript, to
  Dr. Marvin Simon of JPL and to Professor George L. Turin of University of\r\nCalifornia,
  Berkeley. The junior author also gratefully acknowledges the role of the latter
  as her M.S. research\r\nadvisor on the project which formed the nucleus of this
  work. \r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: David
  full_name: Kirkpatrick, David
  last_name: Kirkpatrick
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
citation:
  ama: 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>
  apa: Edelsbrunner, H., Kirkpatrick, D., &#38; Seidel, R. (1983). On the shape of
    a set of points in the plane. <i>IEEE Transactions on Information Theory</i>.
    IEEE. <a href="https://doi.org/10.1109/TIT.1983.1056714 ">https://doi.org/10.1109/TIT.1983.1056714
    </a>
  chicago: Edelsbrunner, Herbert, David Kirkpatrick, and Raimund Seidel. “On the Shape
    of a Set of Points in the Plane.” <i>IEEE Transactions on Information Theory</i>.
    IEEE, 1983. <a href="https://doi.org/10.1109/TIT.1983.1056714 ">https://doi.org/10.1109/TIT.1983.1056714
    </a>.
  ieee: H. Edelsbrunner, D. Kirkpatrick, and R. Seidel, “On the shape of a set of
    points in the plane,” <i>IEEE Transactions on Information Theory</i>, vol. 29,
    no. 4. IEEE, pp. 551–559, 1983.
  ista: 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.
  mla: Edelsbrunner, Herbert, et al. “On the Shape of a Set of Points in the Plane.”
    <i>IEEE Transactions on Information Theory</i>, 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>.
  short: H. Edelsbrunner, D. Kirkpatrick, R. Seidel, IEEE Transactions on Information
    Theory 29 (1983) 551–559.
date_created: 2018-12-11T12:07:06Z
date_published: 1983-06-01T00:00:00Z
date_updated: 2022-01-25T12:55:07Z
day: '01'
doi: '10.1109/TIT.1983.1056714 '
extern: '1'
intvolume: '        29'
issue: '4'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/1056714
month: '06'
oa_version: None
page: 551 - 559
publication: IEEE Transactions on Information Theory
publication_identifier:
  eissn:
  - 1558-0814
  issn:
  - 0018-9162
publication_status: published
publisher: IEEE
publist_id: '1995'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the shape of a set of points in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 29
year: '1983'
...