---
_id: '4095'
abstract:
- lang: eng
  text: he kth-order Voronoi diagram of a finite set of sites in the Euclidean plane
    E2 subdivides E2 into maximal regions such that all points within a given region
    have the same k nearest sites. Two versions of an algorithm are developed for
    constructing the kth-order Voronoi diagram of a set of n sites in O(n2 log n +
    k(n - k) log2 n) time, O(k(n - k)) storage, and in O(n2 + k(n - k) log2 n) time,
    O(n2) storage, respectively.
acknowledgement: 'We would like to thank two anonymous referees for their constructive
  criticism. '
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Chazelle B, Edelsbrunner H. An improved algorithm for constructing kth-order
    Voronoi diagrams. <i>IEEE Transactions on Computers</i>. 1987;36(11):1349-1354.
    doi:<a href="https://doi.org/10.1109/TC.1987.5009474">10.1109/TC.1987.5009474</a>
  apa: Chazelle, B., &#38; Edelsbrunner, H. (1987). An improved algorithm for constructing
    kth-order Voronoi diagrams. <i>IEEE Transactions on Computers</i>. IEEE. <a href="https://doi.org/10.1109/TC.1987.5009474">https://doi.org/10.1109/TC.1987.5009474</a>
  chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for
    Constructing Kth-Order Voronoi Diagrams.” <i>IEEE Transactions on Computers</i>.
    IEEE, 1987. <a href="https://doi.org/10.1109/TC.1987.5009474">https://doi.org/10.1109/TC.1987.5009474</a>.
  ieee: B. Chazelle and H. Edelsbrunner, “An improved algorithm for constructing kth-order
    Voronoi diagrams,” <i>IEEE Transactions on Computers</i>, vol. 36, no. 11. IEEE,
    pp. 1349–1354, 1987.
  ista: Chazelle B, Edelsbrunner H. 1987. An improved algorithm for constructing kth-order
    Voronoi diagrams. IEEE Transactions on Computers. 36(11), 1349–1354.
  mla: Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for Constructing
    Kth-Order Voronoi Diagrams.” <i>IEEE Transactions on Computers</i>, vol. 36, no.
    11, IEEE, 1987, pp. 1349–54, doi:<a href="https://doi.org/10.1109/TC.1987.5009474">10.1109/TC.1987.5009474</a>.
  short: B. Chazelle, H. Edelsbrunner, IEEE Transactions on Computers 36 (1987) 1349–1354.
date_created: 2018-12-11T12:06:54Z
date_published: 1987-11-01T00:00:00Z
date_updated: 2022-02-04T10:32:27Z
day: '01'
doi: 10.1109/TC.1987.5009474
extern: '1'
intvolume: '        36'
issue: '11'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/5009474
month: '11'
oa_version: None
page: 1349 - 1354
publication: IEEE Transactions on Computers
publication_identifier:
  eissn:
  - 1557-9956
  issn:
  - 0018-9340
publication_status: published
publisher: IEEE
publist_id: '2026'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An improved algorithm for constructing kth-order Voronoi diagrams
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 36
year: '1987'
...