## Voronoi DiagramsLet There is also a
## Properties of Voronoi Diagrams- A Voronoi diagram has a graph-like structure:
- The
**nodes**are the points`p` with`|close(p)|>=3` . - The
**edges**are the maximal connected sets of points`p` with`|close(p)|=2` . - The
**faces**are the maximal connected sets of points`p` with`|close(p)|=1.` .
- The
- Let
`e` be an edge of the Voronoi diagram such that`s` and`t` are the two sites of`S` with`close(p)={s,t}` for all points of`e` . Then`e` is a straight line segment contained in the perpendicular bisector of`s` and`t` . - Consider a face
`f` of the Voronoi diagram and let`s` be the site such that`close(p)={s}` for all points of`f` .- The distance of all points of
`f` to s is smaller than to all other sites. `f` contains`s` .`f` is an open convex polygonal region.
- The distance of all points of
## Representation of Voronoi DiagramsVoronoi diagrams are represented by parameterized
plane map of type - There is a node in the graph for every node of the Voronoi diagram.
- We place a "node at infinity" on every unbounded edge of the Voronoi diagram.
- There is an edge in the graph for every edge of the Voronoi diagram.
- Every edge is labeled with the site whose region lies to the left. See also Orientation and Sidedness.
- Every proper node
`v` is labeled by a`CIRCLE(a,b,c)` where`a,b,c` are distinct sites whose regions are incident to`v` . The center of the circle is the position of`v` in the plane. - Every node
`v` at infinity lies on the perpendicular bisector of two sites`a` and`b` .`v` is labeled by`CIRCLE(a,x,b)` where`x` is an arbitrary point collinear with`a` and`b` and`v` lies to the left of the oriented segment from`a` to`b` .
## Running TimeThe running time of the algorithms for computing Voronoi diagrams isO(nlogn).
## Verification of Voronoi DiagramsThe functionbool Is_Voronoi_Diagram(const GRAPH<CIRCLE,POINT>& G, delaunay_voronoi_kind kind)checks whether `G` is a Voronoi Diagram of the points associated
with its nodes. The flag `kind` allows to choose between the nearest
(`kind=NEAREST` ) and furthest (`kind=FURTHEST` ) site
version. See also Verification of Geometric
Structures. |
## See also:
## Applications:
## Manual Entries |

Please send any suggestions, comments or questions to leda@algorithmic-solutions.com

© Copyright 2001-2003, Algorithmic Solutions Software GmbH