Citizendia
Your Ad Here

The Voronoi diagram of a random set of points in the plane (all points lie within the image).
The Voronoi diagram of a random set of points in the plane (all points lie within the image).

In mathematics, a Voronoi diagram, named after Georgy Voronoi, also called a Voronoi tessellation, a Voronoi decomposition, or a Dirichlet tessellation (after Lejeune Dirichlet), is a special kind of decomposition of a metric space determined by distances to a specified discrete set of objects in the space, e. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Georgy Feodosevich Voronoy (Георгий Феодосьевич Вороной 28 April 1868 &ndash 20 November 1908) was a famous Russian A tessellation or tiling of the plane is a collection of Plane figures that fills the plane with no overlaps and no gaps Johann Peter Gustav Lejeune Dirichlet (ləʒœn diʀiçle February 13, 1805 &ndash May 5, 1859) was a German Mathematician In Mathematics, a metric space is a set where a notion of Distance (called a metric) between elements of the set is defined In Topology, a branch of Mathematics, a point x of a set S is called an isolated point,if there exists a neighborhood of g. , by a discrete set of points.

In the simplest and most common case, in the plane, we are given a set of points S, and the Voronoi diagram for S is the partition of the plane which associates a region V(p) with each point p from S in such a way that all points in V(p) are closer to p than to any other point in S.

Contents

Definition

For any (topologically) discrete set S of points in Euclidean space and for almost any point x, there is one point of S closest to x. Topology ( Greek topos, "place" and logos, "study" is the branch of Mathematics that studies the properties of The word "almost" is used to indicate exceptions where a point x may be equally close to two or more points of S.

If S contains only two points, a and b, then the set of all points equidistant from a and b is a hyperplane—an affine subspace of codimension 1. A hyperplane is a concept in Geometry. It is a higher-dimensional generalization of the concepts of a line in Euclidean plane geometry and a In Mathematics, an affine space is an abstract structure that generalises the affine-geometric properties of Euclidean space. In Mathematics, codimension is a basic geometric idea that applies to Subspaces in Vector spaces and more generally to Submanifolds in Manifolds That hyperplane is the boundary between the set of all points closer to a than to b, and the set of all points closer to b than to a. It is the perpendicular bisector of the line segment from a and b. In Geometry, bisection is the division of something into two equal or Congruent parts usually by a line, which is then called a bisector

In general, the set of all points closer to a point c of S than to any other point of S is the interior of a (in some cases unbounded) convex polytope called the Dirichlet domain or Voronoi cell for c. In Geometry, polytope is a generic term that can refer to a two-dimensional Polygon, a three-dimensional Polyhedron, or any of the various generalizations The set of such polytopes tessellates the whole space, and is the Voronoi tessellation corresponding to the set S. A tessellation or tiling of the plane is a collection of Plane figures that fills the plane with no overlaps and no gaps If the dimension of the space is only 2, then it is easy to draw pictures of Voronoi tessellations, and in that case they are sometimes called Voronoi diagrams.

Properties

History

Informal use of Voronoi diagrams can be traced back to Descartes in 1644. Dirichlet used 2-dimensional and 3-dimensional Voronoi diagrams in his study of quadratic forms in 1850. Johann Peter Gustav Lejeune Dirichlet (ləʒœn diʀiçle February 13, 1805 &ndash May 5, 1859) was a German Mathematician British physician John Snow used a Voronoi diagram in 1854 to illustrate how the majority of people who died in the Soho cholera epidemic lived closer to the infected Broad Street pump than to any other water pump. John Snow ( 15 March 1813 &ndash 16 June 1858) was a British physician and a leader in the adoption of Anaesthesia and medical This article is about an area of Manhattan, New York City. For the area in London UK see Soho.

Voronoi diagrams are named after Russian mathematician Georgy Fedoseevich Voronoi (or Voronoy) who defined and studied the general n-dimensional case in 1908. Georgy Feodosevich Voronoy (Георгий Феодосьевич Вороной 28 April 1868 &ndash 20 November 1908) was a famous Russian Voronoi diagrams that are used in geophysics and meteorology to analyse spatially distributed data (such as rainfall measurements) are called Thiessen polygons after American meteorologist Alfred H. Thiessen. Geophysics, a major discipline of Earth sciences, is the study of the Earth by quantitative physical methods especially by seismic, electromagnetic Meteorology (from Greek grc μετέωρος metéōros, "high in the sky" and grc -λογία -logia) is the Interdisciplinary In condensed matter physics, such tessellations are also known as Wigner-Seitz unit cells. Condensed matter physics is the field of Physics that deals with the macroscopic physical properties of Matter. The Wigner-Seitz cell (named after E P Wigner and Frederick Seitz) is a geometrical construction which helps in the study of Crystalline material in Voronoi tessellations of the reciprocal lattice of momenta are called Brillouin zones. In Crystallography, the reciprocal lattice of a Bravais lattice is the set of all vectors K such that e^{i\mathbf{K}\cdot\mathbf{R}}=1 In Classical mechanics, momentum ( pl momenta SI unit kg · m/s, or equivalently N · s) is the product In Mathematics and Solid state physics, the first Brillouin zone is a uniquely defined Primitive cell of the Reciprocal lattice in the For general lattices in Lie groups, the cells are simply called fundamental domains. In Mathematics, a Lie group (ˈliː sounds like "Lee" is a group which is also a Differentiable manifold, with the property that the group In Geometry, the fundamental domain of a Symmetry group of an object or pattern is a part of the pattern as small as possible which based on the Symmetry In the case of general metric spaces, the cells are often called metric fundamental polygons. In Mathematics, a metric space is a set where a notion of Distance (called a metric) between elements of the set is defined In Mathematics, each closed Surface in the sense of Geometric topology can be constructed from an even-sided oriented Polygon, called a fundamental

Examples

This is a slice of the Voronoi diagram of a random set of points in a 3D box. In general a cross section of a 3D Voronoi tessellation is not a 2D Voronoi tessellation itself. (The cells are all convex polyhedra.)
This is a slice of the Voronoi diagram of a random set of points in a 3D box. In general a cross section of a 3D Voronoi tessellation is not a 2D Voronoi tessellation itself. (The cells are all convex polyhedra. In Euclidean space, an object is convex if for every pair of points within the object every point on the Straight line segment that joins them is also within the What is a polyhedron? We can at least say that a polyhedron is built up from different kinds of element or entity each associated with a different number of dimensions )

Voronoi tessellations of regular lattices of points in two or three dimensions give rise to many familiar tessellations. In Mathematics, especially in Geometry and Group theory, a lattice in R n is a Discrete subgroup of

For the set of points (x, y) with x in a discrete set X and y in a discrete set Y, we get rectangular tiles with the points not necessarily at their centers. The cubic crystal system (or isometric) is a Crystal system where the Unit cell is in the shape of a Cube. The rhombic dodecahedron is a convex Polyhedron with 12 rhombic faces The cubic crystal system (or isometric) is a Crystal system where the Unit cell is in the shape of a Cube. The truncated octahedron is an Archimedean solid. It has 8 regular hexagonal faces 6 regular square faces 24 vertices and 36 edges

Generalizations

Voronoi cells can be defined for metrics other than Euclidean (such as the Mahalanobis or Manhattan distances). In Statistics, Mahalanobis distance is a Distance measure introduced by P Taxicab geometry, considered by Hermann Minkowski in the 19th century is a form of Geometry in which the usual metric of Euclidean geometry However in these cases the Voronoi tessellation is not guaranteed to exist (or to be a "true" tessellation), since the equidistant locus for two points may fail to be subspace of codimension 1, even in the 2-dimensional case.

Voronoi cells can also be defined by measuring distances to objects that are not points. The Voronoi diagram with these cells is also called the medial axis. The medial axis is a method for representing the Shape of objects by finding the Topological skeleton, a set of curves which roughly run along the middle of an object Even when the objects are line segments, the Voronoi cells are not bounded by straight lines. The medial axis is used in image segmentation, optical character recognition and other computational applications. Optical character recognition, usually abbreviated to OCR, is the Mechanical or electronic translation of Images of handwritten typewritten In materials science, polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations. A simplified version of the Voronoi diagram of line segments is the straight skeleton. In Geometry, a straight skeleton is a method of representing a Polygon by a Topological skeleton.

Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.
Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.

The Voronoi diagram of n points in d-dimensional space requires O(n^{\lceil d/2 \rceil}) storage space. Therefore, Voronoi diagrams are often not feasible for d>2. An alternative is to use approximate Voronoi diagrams, where the Voronoi cells have a fuzzy boundary, which can be approximated. [1]

Application

A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where you want to find the object that is closest to a given query point. The point location problem is a fundamental topic of Computational geometry. Nearest neighbor queries have numerous applications. For example, when you want to find the nearest hospital, or the most similar object in a database. A Computer Database is a structured collection of records or data that is stored in a computer system

The Voronoi diagram is useful in polymer physics. It can be used to represent free volume of the polymer.

It is also used in derivations of the capacity of a wireless network. Wireless network refers to any type of Computer network that is Wireless, and is commonly associated with a Telecommunications network whose interconnections

In climatology, Voronoi diagrams are used to calculate the rainfall of an area, based on a series of point measurements. In this usage, they are generally referred to as Thiessen polygons.

Voronoi diagrams are also used in computer graphics to procedurally generate some kinds of organic looking textures.

See also

References

  1. ^ S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721-730.

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic