Voronoi cells: Difference between revisions
Jump to navigation
Jump to search
m (Placed external links at foot of page.) |
Carl McBride (talk | contribs) m (Added a recent publication) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
A '''Voronoi cell''' <ref>[http://dx.doi.org/10.1515/crll.1908.134.198 G. F. Voronoi "Nouvelles applications des paramètres continus à la théorie des formes quadratiques - Deuxième mémoire", Journal für die reine und angewandte Mathematik '''134''' pp. 198-287 (1908)]</ref>(also known as: '''Voronoi polyhedra''', '''Voronoi tessellations''', '''Dirichlet tesselations''', '''Wigner-Seitz cells''') is the diagram that results when a cell is defined around each of the points (or nodes, | |||
A '''Voronoi cell''' (also known as: '''Voronoi polyhedra''', '''Voronoi tessellations''', '''Dirichlet tesselations''', '''Wigner-Seitz cells''') | |||
is the diagram that results when a cell is defined around each of the points (or nodes, | |||
or vertices) of a network with the following criterion: each point in the cell is closer to its node | or vertices) of a network with the following criterion: each point in the cell is closer to its node | ||
than to any of the others. This very intuitive partition of space results in the Voronoi tessellation. The | than to any of the others. This very intuitive partition of space results in the Voronoi tessellation. The | ||
| Line 9: | Line 7: | ||
Voronoi cells are [[dual lattice | dual]] of [[Delaunay simplexes]]. | Voronoi cells are [[dual lattice | dual]] of [[Delaunay simplexes]]. | ||
==Algorithms== | ==Algorithms== | ||
*[http://dx.doi.org/10.1016/0021-9991(78)90110-9 Witold Brostow, Jean-Pierre Dussault and Bennett L. Fox "Construction of Voronoi polyhedra", Journal of Computational Physics '''29''' pp. 81-92 (1978)] | |||
*[http://dx.doi.org/10.1016/0021-9991(79)90146-3 J. L. Finney "A procedure for the construction of Voronoi polyhedra", Journal of Computational Physics '''32''' pp. 137-143 (1979)] | |||
*[http://dx.doi.org/10.1016/0021-9991(83)90087-6 Masaharu Tanemura, Tohru Ogawa and Naofumi Ogita "A new algorithm for three-dimensional voronoi tessellation", Journal of Computational Physics '''51''' pp. 191-207 (1983)] | |||
*[http://dx.doi.org/10.1016/0021-9991(86)90123-3 N. N. Medvedev "The algorithm for three-dimensional voronoi polyhedra", Journal of Computational Physics '''67''' pp. 223-229 (1986)] | |||
==References== | ==References== | ||
<references/> | |||
'''Related reading''' | |||
*[http://dx.doi.org/10.1063/1.438311 C. S. Hsu and Aneesur Rahman "Interaction potentials and their effect on crystal nucleation and symmetry", Journal of Chemical Physics '''71''' pp. 4974-4986 (1979)] | |||
*[http://dx.doi.org/10.1063/1.442299 J. Neil Cape, John L. Finney and Leslie V. Woodcock "An analysis of crystallization by homogeneous nucleation in a 4000-atom soft-sphere model", Journal of Chemical Physics '''75''' pp. 2366-2373 (1981)] | |||
*[http://dx.doi.org/10.1063/1.459711 Nikolai N. Medvedev, Alfons Geiger and Witold Brostow "Distinguishing liquids from amorphous solids: Percolation analysis on the Voronoi network", Journal of Chemical Physics '''93''' pp. 8337-8342 (1990)] | |||
*[http://dx.doi.org/10.1021/j100118a044 J. C. Gil Montoro and J. L. F. Abascal "The Voronoi polyhedra as tools for structure determination in simple disordered systems", Journal of Physical Chemistry '''97''' pp. 4211 - 4215 (1993)] | |||
*[http://dx.doi.org/10.1063/1.2011390 V. Senthil Kumar and V. Kumaran "Voronoi cell volume distribution and configurational entropy of hard-spheres", Journal of Chemical Physics '''123''' 114501 (2005)] | |||
==External links== | *[http://dx.doi.org/10.1063/1.2000233 V. Senthil Kumar and V. Kumaran "Voronoi neighbor statistics of hard-disks and hard-spheres", Journal of Chemical Physics '''123''' 074502 (2005)] | ||
*[http://dx.doi.org/10.1063/1.3382485 Jagtar Singh Hunjan and Byung Chan Eu "The Voronoi volume and molecular representation of molar volume: Equilibrium simple fluids", Journal of Chemical Physics '''132''' 134510 (2010)] | |||
==External links and resources== | |||
*[http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html#part_IX The CGAL project on computational geometry] | *[http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html#part_IX The CGAL project on computational geometry] | ||
*[ftp://ftp.dl.ac.uk/ccp5/ALLEN_TILDESLEY/F.35 The Voronoi construction in 2d and 3d] sample FORTRAN computer code from the book [http://www.oup.com/uk/catalogue/?ci=9780198556459 M. P. Allen and D. J. Tildesley "Computer Simulation of Liquids", Oxford University Press (1989)]. | |||
[[category: Computer simulation techniques ]] [[category: Mathematics ]] | [[category: Computer simulation techniques ]] [[category: Mathematics ]] | ||
Latest revision as of 10:32, 7 April 2010
A Voronoi cell [1](also known as: Voronoi polyhedra, Voronoi tessellations, Dirichlet tesselations, Wigner-Seitz cells) is the diagram that results when a cell is defined around each of the points (or nodes, or vertices) of a network with the following criterion: each point in the cell is closer to its node than to any of the others. This very intuitive partition of space results in the Voronoi tessellation. The typical example is to, e.g., assign areas of a country to different fire stations, so that if a fire occurs, the corresponding station is the closest one.
Voronoi cells are dual of Delaunay simplexes.
Algorithms[edit]
- Witold Brostow, Jean-Pierre Dussault and Bennett L. Fox "Construction of Voronoi polyhedra", Journal of Computational Physics 29 pp. 81-92 (1978)
- J. L. Finney "A procedure for the construction of Voronoi polyhedra", Journal of Computational Physics 32 pp. 137-143 (1979)
- Masaharu Tanemura, Tohru Ogawa and Naofumi Ogita "A new algorithm for three-dimensional voronoi tessellation", Journal of Computational Physics 51 pp. 191-207 (1983)
- N. N. Medvedev "The algorithm for three-dimensional voronoi polyhedra", Journal of Computational Physics 67 pp. 223-229 (1986)
References[edit]
Related reading
- C. S. Hsu and Aneesur Rahman "Interaction potentials and their effect on crystal nucleation and symmetry", Journal of Chemical Physics 71 pp. 4974-4986 (1979)
- J. Neil Cape, John L. Finney and Leslie V. Woodcock "An analysis of crystallization by homogeneous nucleation in a 4000-atom soft-sphere model", Journal of Chemical Physics 75 pp. 2366-2373 (1981)
- Nikolai N. Medvedev, Alfons Geiger and Witold Brostow "Distinguishing liquids from amorphous solids: Percolation analysis on the Voronoi network", Journal of Chemical Physics 93 pp. 8337-8342 (1990)
- J. C. Gil Montoro and J. L. F. Abascal "The Voronoi polyhedra as tools for structure determination in simple disordered systems", Journal of Physical Chemistry 97 pp. 4211 - 4215 (1993)
- V. Senthil Kumar and V. Kumaran "Voronoi cell volume distribution and configurational entropy of hard-spheres", Journal of Chemical Physics 123 114501 (2005)
- V. Senthil Kumar and V. Kumaran "Voronoi neighbor statistics of hard-disks and hard-spheres", Journal of Chemical Physics 123 074502 (2005)
- Jagtar Singh Hunjan and Byung Chan Eu "The Voronoi volume and molecular representation of molar volume: Equilibrium simple fluids", Journal of Chemical Physics 132 134510 (2010)
External links and resources[edit]
- The CGAL project on computational geometry
- The Voronoi construction in 2d and 3d sample FORTRAN computer code from the book M. P. Allen and D. J. Tildesley "Computer Simulation of Liquids", Oxford University Press (1989).