Namespaces
Variants
Actions

Difference between revisions of "Voronoi diagram"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
v1100701.png
 +
$#A+1 = 14 n = 0
 +
$#C+1 = 14 : ~/encyclopedia/old_files/data/V110/V.1100070 Vorono\Aui diagram
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A very important geometric structure in [[Computational geometry|computational geometry]], named after G.F. Voronoi. The earliest significant use of Voronoi diagrams seems to have occurred in the work of C.F. Gauss, P.G.L. Dirichlet and Voronoi on the reducibility of positive-definite quadratic forms (cf. [[Quadratic form|Quadratic form]]).
 
A very important geometric structure in [[Computational geometry|computational geometry]], named after G.F. Voronoi. The earliest significant use of Voronoi diagrams seems to have occurred in the work of C.F. Gauss, P.G.L. Dirichlet and Voronoi on the reducibility of positive-definite quadratic forms (cf. [[Quadratic form|Quadratic form]]).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100701.png" /> be a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100702.png" /> points in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100703.png" />. The Voronoi diagram generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100704.png" /> is the partition of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100705.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100706.png" /> convex cells, the Voronoi cells, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100707.png" />, where each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100708.png" /> contains all points of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v1100709.png" /> closer to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v11007010.png" /> than to any other point:
+
Let $  S = \{ p _ {1} \dots p _ {n} \} $
 +
be a set of $  n $
 +
points in $  \mathbf R  ^ {d} $.  
 +
The Voronoi diagram generated by $  S $
 +
is the partition of the $  \mathbf R  ^ {d} $
 +
into $  n $
 +
convex cells, the Voronoi cells, $  V _ {i} $,  
 +
where each $  V _ {i} $
 +
contains all points of $  \mathbf R  ^ {d} $
 +
closer to $  p _ {i} $
 +
than to any other point:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v11007011.png" /></td> </tr></table>
+
$$
 +
V _ {i} = \left \{ x : {\forall j \neq i,  d ( x,p _ {i} ) \leq  d ( x,p _ {j} ) } \right \} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v11007012.png" /> is the Euclidean distance between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v11007013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110070/v11007014.png" />.
+
where $  d ( x,y ) $
 +
is the Euclidean distance between $  x $
 +
and $  y $.
  
 
See also [[Delaunay triangulation|Delaunay triangulation]].
 
See also [[Delaunay triangulation|Delaunay triangulation]].

Latest revision as of 08:28, 6 June 2020


A very important geometric structure in computational geometry, named after G.F. Voronoi. The earliest significant use of Voronoi diagrams seems to have occurred in the work of C.F. Gauss, P.G.L. Dirichlet and Voronoi on the reducibility of positive-definite quadratic forms (cf. Quadratic form).

Let $ S = \{ p _ {1} \dots p _ {n} \} $ be a set of $ n $ points in $ \mathbf R ^ {d} $. The Voronoi diagram generated by $ S $ is the partition of the $ \mathbf R ^ {d} $ into $ n $ convex cells, the Voronoi cells, $ V _ {i} $, where each $ V _ {i} $ contains all points of $ \mathbf R ^ {d} $ closer to $ p _ {i} $ than to any other point:

$$ V _ {i} = \left \{ x : {\forall j \neq i, d ( x,p _ {i} ) \leq d ( x,p _ {j} ) } \right \} , $$

where $ d ( x,y ) $ is the Euclidean distance between $ x $ and $ y $.

See also Delaunay triangulation.

References

[a1] F.P. Preparata, M.I. Shamos, "Computational geometry: an introduction" , Springer (1985) MR805539 Zbl 0575.68059 Zbl 0759.68037
[a2] H. Edelsbrunner, "Algorithms in combinatorial geometry" , Springer (1987) MR0904271 Zbl 0634.52001
[a3] A. Okabe, B. Boots, K. Sugihara, "Spatial tessellations: concepts and applications of Voronoi diagrams" , Wiley (1992) MR1210959 Zbl 0877.52010
[a4] G.F. Voronoi, "Nouvelles applications des parametres continus a la theorie des formes quadratiques" J. Reine Angew. Math. , 134 (1908) pp. 198–287 Zbl 38.0261.01 Zbl 39.0274.01
How to Cite This Entry:
Voronoi diagram. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Voronoi_diagram&oldid=24136
This article was adapted from an original article by O.R. Musin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article