Voronoi cells - Revision history

Carl McBride: Added a recent publication

2010-04-07T09:32:30Z

Added a recent publication

← Older revision		Revision as of 11:32, 7 April 2010
Line 1:		Line 1:
	A '''Voronoi cell''' (also known as: '''Voronoi polyhedra''', '''Voronoi tessellations''', '''Dirichlet tesselations''', '''Wigner-Seitz cells''').		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,
	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 8:		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(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(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(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)]		*[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==
	~~# 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)~~		<references/>
	#[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)]		'''Related reading'''
	#[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.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.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.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.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.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.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)]		*[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.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.2011390 V. Senthil Kumar and V. Kumaran "Voronoi cell volume distribution and configurational entropy of hard-spheres", Journal of Chemical Physics '''123''' 114501 (2005)]
			*[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==		==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)].		*[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 ]]

Nice and Tidy: Added link to code F.35

2009-02-08T17:37:06Z

Added link to code F.35

← Older revision		Revision as of 19:37, 8 February 2009
Line 1:		Line 1:
	~~{{Stub-general}}~~
	A '''Voronoi cell''' (also known as: '''Voronoi polyhedra''', '''Voronoi tessellations''', '''Dirichlet tesselations''', '''Wigner-Seitz cells''').		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,		is the diagram that results when a cell is defined around each of the points (or nodes,
Line 21:		Line 20:
	#[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)]		#[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)]
	#[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.2000233 V. Senthil Kumar and V. Kumaran "Voronoi neighbor statistics of hard-disks and hard-spheres", Journal of Chemical Physics '''123''' 074502 (2005)]
	==External links==		==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 ]]

Nice and Tidy: Placed external links at foot of page.

2008-12-11T18:23:51Z

Placed external links at foot of page.

← Older revision		Revision as of 20:23, 11 December 2008
Line 13:		Line 13:
	#[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(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)]		#[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)]
	~~==External links==~~
	*[http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html#part_IX The CGAL project on computational geometry]
	==References==		==References==
	# 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)		# 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)
Line 23:		Line 21:
	#[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)]		#[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)]
	#[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.2000233 V. Senthil Kumar and V. Kumaran "Voronoi neighbor statistics of hard-disks and hard-spheres", Journal of Chemical Physics '''123''' 074502 (2005)]
			==External links==
			*[http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html#part_IX The CGAL project on computational geometry]
	[[category: Computer simulation techniques ]] [[category: Mathematics ]]		[[category: Computer simulation techniques ]] [[category: Mathematics ]]

Carl McBride at 15:39, 21 February 2008

2008-02-21T15:39:31Z

← Older revision		Revision as of 17:39, 21 February 2008
Line 1:		Line 1:
	{{Stub-general}}		{{Stub-general}}
	~~The~~ '''Voronoi ~~cells~~''' or '''Voronoi ~~tessellation~~''' or '''Dirichlet ~~tesselation~~''' or '''Wigner-Seitz cells'''.		A '''Voronoi cell''' (also known as: '''Voronoi polyhedra''', '''Voronoi tessellations''', '''Dirichlet tesselations''', '''Wigner-Seitz cells''').
	~~This~~ is the diagram that results when a cell is defined around each of the points (or nodes,		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

Carl McBride at 14:59, 21 February 2008

2008-02-21T14:59:01Z

← Older revision		Revision as of 16:59, 21 February 2008
Line 8:		Line 8:

	Voronoi cells are [[dual lattice \| dual]] of [[Delaunay simplexes]].		Voronoi cells are [[dual lattice \| dual]] of [[Delaunay simplexes]].
			==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)]
	==External links==		==External links==
	*[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]
	==References==		==References==
	# 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)		# 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)
	#[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.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.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.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)]

Dduque: Also belongs to category: Mathematics , I guess

2008-02-18T10:30:24Z

Also belongs to category: Mathematics , I guess

← Older revision		Revision as of 12:30, 18 February 2008
Line 23:		Line 23:
	#[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)]		#[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)]
	#[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.2000233 V. Senthil Kumar and V. Kumaran "Voronoi neighbor statistics of hard-disks and hard-spheres", Journal of Chemical Physics '''123''' 074502 (2005)]
	[[category: Computer simulation techniques]]		[[category: Computer simulation techniques ]] [[category: Mathematics ]]

Dduque: added link to dual

2007-10-30T13:15:24Z

added link to dual

← Older revision		Revision as of 15:15, 30 October 2007
Line 7:		Line 7:
	occurs, the corresponding station is the closest one.		occurs, the corresponding station is the closest one.

	Voronoi cells are ~~'''~~dual~~'''~~ of [[Delaunay simplexes]].		Voronoi cells are [[dual lattice \| dual]] of [[Delaunay simplexes]].

Dduque at 10:26, 11 October 2007

2007-10-11T10:26:03Z

← Older revision		Revision as of 12:26, 11 October 2007
Line 1:		Line 1:
	{{Stub-general}}		{{Stub-general}}
	The '''Voronoi cells''' or '''Voronoi tessellation''' or '''Dirichlet tesselation''' or '''Wigner-Seitz cells'''.		The '''Voronoi cells''' or '''Voronoi tessellation''' or '''Dirichlet tesselation''' or '''Wigner-Seitz cells'''.
	~~==See also==~~		This is the diagram that results when a cell is defined around each of the points (or nodes,
	*[[Delaunay simplexes]]		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]].


	==External links==		==External links==
	*[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]

Carl McBride at 13:28, 27 September 2007

2007-09-27T13:28:36Z

← Older revision		Revision as of 15:28, 27 September 2007
Line 1:		Line 1:
			{{Stub-general}}
	The '''Voronoi cells''' or '''Voronoi tessellation''' or '''Dirichlet tesselation''' or '''Wigner-Seitz cells'''.		The '''Voronoi cells''' or '''Voronoi tessellation''' or '''Dirichlet tesselation''' or '''Wigner-Seitz cells'''.
	==See also==		==See also==

Nice and Tidy at 14:56, 13 September 2007

2007-09-13T14:56:13Z

← Older revision		Revision as of 16:56, 13 September 2007
Line 2:		Line 2:
	==See also==		==See also==
	*[[Delaunay simplexes]]		*[[Delaunay simplexes]]
			==External links==
			*[http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/packages.html#part_IX The CGAL project on computational geometry]
	==References==		==References==
	# 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)		# 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)