---
_id: '4125'
abstract:
- lang: eng
  text: "Let S denote a set of n points in the plane such that each point p has assigned
    a positive weight w(p) which expresses its capability to influence its neighbourhood.
    In this sense, the weighted distance of an arbitrary point x from p is given by
    de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi
    diagram for S is a subdivision of the plane such that each point p in S is associated
    with a region consisting of all points x in the plane for which p is a weighted
    nearest point of S.\r\n\r\nAn algorithm which constructs the weighted Voronoi
    diagram for S in O(n2) time is outlined in this paper. The method is optimal as
    the diagram can consist of Θ(n2) faces, edges and vertices.\r\n"
acknowledgement: The second author gratefully acknowledges discussions on the presented
  topic with David Kirkpatrick and Raimund Seidel.
article_processing_charge: No
article_type: original
author:
- first_name: Franz
  full_name: Aurenhammer, Franz
  last_name: Aurenhammer
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted
    Voronoi diagram in the plane. <i>Pattern Recognition</i>. 1983;17(2):251-257.
    doi:<a href="https://doi.org/10.1016/0031-3203(84)90064-5">10.1016/0031-3203(84)90064-5</a>
  apa: Aurenhammer, F., &#38; Edelsbrunner, H. (1983). An optimal algorithm for constructing
    the weighted Voronoi diagram in the plane. <i>Pattern Recognition</i>. Elsevier.
    <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>
  chicago: Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for
    Constructing the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>.
    Elsevier, 1983. <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>.
  ieee: F. Aurenhammer and H. Edelsbrunner, “An optimal algorithm for constructing
    the weighted Voronoi diagram in the plane,” <i>Pattern Recognition</i>, vol. 17,
    no. 2. Elsevier, pp. 251–257, 1983.
  ista: Aurenhammer F, Edelsbrunner H. 1983. An optimal algorithm for constructing
    the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.
  mla: Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing
    the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>, vol. 17,
    no. 2, Elsevier, 1983, pp. 251–57, doi:<a href="https://doi.org/10.1016/0031-3203(84)90064-5">10.1016/0031-3203(84)90064-5</a>.
  short: F. Aurenhammer, H. Edelsbrunner, Pattern Recognition 17 (1983) 251–257.
date_created: 2018-12-11T12:07:05Z
date_published: 1983-07-01T00:00:00Z
date_updated: 2022-01-27T14:06:27Z
day: '01'
doi: 10.1016/0031-3203(84)90064-5
extern: '1'
intvolume: '        17'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0031320384900645?via%3Dihub
month: '07'
oa_version: None
page: 251 - 257
publication: Pattern Recognition
publication_identifier:
  eissn:
  - 1873-5142
  issn:
  - 0031-3203
publication_status: published
publisher: Elsevier
publist_id: '1997'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An optimal algorithm for constructing the weighted Voronoi diagram in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 17
year: '1983'
...