---
_id: '4108'
abstract:
- lang: eng
text: We propose a uniform and general framework for defining and dealing with Voronoi
diagrams. In this framework a Voronoi diagram is a partition of a domainD induced
by a finite number of real valued functions onD. Valuable insight can be gained
when one considers how these real valued functions partitionD ×R. With this view
it turns out that the standard Euclidean Voronoi diagram of point sets inR d along
with its order-k generalizations are intimately related to certain arrangements
of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms.
We also discuss how the formalism of arrangements can be used to solve certain
intersection and union problems.
acknowledgement: 'We would like to thank John Gilbert for his careful reading of the
manuscript and his many suggestions for improvement. We also want to thank Bennett
Battaile, Gianfranco Bilardi, Joseph O''Rourke, and Chee Yap for their comments. '
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: Raimund
full_name: Seidel, Raimund
last_name: Seidel
citation:
ama: Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. Discrete &
Computational Geometry. 1986;1(1):25-44. doi:10.1007/BF02187681
apa: Edelsbrunner, H., & Seidel, R. (1986). Voronoi diagrams and arrangements.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187681
chicago: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
Discrete & Computational Geometry. Springer, 1986. https://doi.org/10.1007/BF02187681.
ieee: H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” Discrete
& Computational Geometry, vol. 1, no. 1. Springer, pp. 25–44, 1986.
ista: Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete
& Computational Geometry. 1(1), 25–44.
mla: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
Discrete & Computational Geometry, vol. 1, no. 1, Springer, 1986, pp.
25–44, doi:10.1007/BF02187681.
short: H. Edelsbrunner, R. Seidel, Discrete & Computational Geometry 1 (1986)
25–44.
date_created: 2018-12-11T12:06:59Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T08:53:39Z
day: '01'
doi: 10.1007/BF02187681
extern: '1'
intvolume: ' 1'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 25 - 44
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2012'
quality_controlled: '1'
status: public
title: Voronoi diagrams and arrangements
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1986'
...