http://www.math.iastate.edu/gunzburg/voronoi.html#anim
from that page: (Centroidal Voronoi Tessellations; territorial behavior of animals)
--------------------------------------------------------------------------------
Centroidal Voronoi Tessellations
--------------------------------------------------------------------------------
A centroidal Voronoi tessellation is a Voronoi tessellation of a given set such that the associated generating points are centroids (centers of mass with respect to a given density function) of the corresponding Voronoi regions. Such tessellations are useful, in among other contexts, in data compression, optimal quadrature rules, optimal representation and quantization, finite difference schemes, optimal distribution of resources, cellular biology, and the territorial behavior of animals. We have studied methods for computing these tessellations, provided some analyses concerning both the tessellations and the methods for their determination, and computed sample tessellations. Details may be found in the paper cited below.
--------------------------------------------------------------------------------
Return to
Max Gunzburger home page
E-mail to Max Gunzburger
gunzburg@iastate.edu
--------------------------------------------------------------------------------
Collaborators
Qiang Du -- Iowa State University and Hong Kong University of Science and Technology
Vance Faber -- Lizardtech, Inc.
--------------------------------------------------------------------------------
Applications
--------------------------------------------------------------------------------
Data compression
We will use a context from image processing; however, the basic ideas and principles are valid for many other data compression applications.
The setting is as follows. We have a color picture composed of many pixels, each of which has an associated color. Each of the colors is a combination of basic, e.g., primary, colors. In a given picture, there may be many different colors. For example, there may be on the order of a million pixels in a picture, with each pixel potentially having a different color. Our task is to approximate the picture by replacing the color at each pixel by one from a smaller set of colors. The natural questions are: how does one choose the smaller, approximating set of colors and how does on assign the colors in the original picture to the colors in approximating set? In a straightforward way, one may use a Monte Carlo method, using the distribution of colors (suitably normalized) as a probability density, to choose the set of approximating colors. Once this set is determined, it is natural to choose the assignment sets to be the associated Voronoi sets (in color space). Unfortunately, even with 256 approximating colors, the approximate pictures produced in this manner are not always satifactory. A better method for choosing the approximating colors is to construct a centroidal Voronoi tessellation of the color space. Then, the centroids of the Voronoi regions are chosen to be the approximating colors and the assignment sets are the corresponding Voronoi regions.
We provide a gray-scale example comparing compressed images found by a Monte Carlo method and by the centroidal Voronoi algorithm. Clearly, the latter is a better approximation of the original picture.
An 8-bit monochrome picture
The compressed 3-bit image by the Monte Carlo simulation
The compressed 3-bit image by the centroidal Voronoi algorithm
--------------------------------------------------------------------------------
Optimal quadrature rules
Consider piecewise constant quadrature rules. Here, we subdivide the region of integration into subregions and approximate the integral by the sum of the products of the volumes of the subregions and the integrand evaluated at a point in the subregion. The optimal error estimate for such a rule is achieved when the subregions are a centroidal Voronoi tessellation with the quadrature points chosen to be the centroids of the subregions. This result can be extended to composite one-point rules involving the evalution of derivatives of the functional.
--------------------------------------------------------------------------------
Optimal representation and quantization
Consider the representation or interpolation of observed data. For example, one of the earliest practical applications of Voronoi diagrams was to the problem of estimating the total precipitation over a period of time in a given geographical region. The best locations for the pluviometers in order to reduce the estimation error is at the centroids of a centroidal Voronoi tessellation of the geographic region. A similar example is the question of round-off, e.g., to represent real numbers by the closest integers. This optimal answer is obviously a simple example of one-dimensional centroidal Voronoi diagrams.
The representation of a given quantity with less information is often referred to as quantization and is an important subject in information theory. The subject of vector quantization has broad applications in signal processing and telecommunication. The image compression example we discussed earlier belongs to this subject as well.
--------------------------------------------------------------------------------
Finite difference schemes having optimal truncation errors
A common way to define finite difference schemes on irregular meshes for the approximate solution of partial differential equations is based on Voronoi tessellations and its dual tessellation, the Delaunay triangulation. In many cases, using centroidal Voronoi tesselations guarantee a second-order truncation error for the difference equations compared to a first-order truncation error for other Voronoi tesselations. Similar results are know for covolume methods based on the dual Voronoi-Delaunay tessellations.
--------------------------------------------------------------------------------
Optimal placement of resources
A typical example among problems dealing with the optimal placement of resources is the placement of mailboxes in a city or neighborhood so as to make them most convenient for users. Consider the following assumptions.
A user will use the mailbox nearest to their home.
The cost (to the user) of using a mailbox is a function of the distance from the user's home to the mailbox.
The total cost to users as a whole is measured by the distance to the neareast mailbox averaged over all users in the region.
The optimal placement of mailboxes is defined to be the one that minimizes the total cost to the users.
Then, it is not difficult to show that the optimal placement of the mailboxes is at the centroids of a centroidal Voronoi tessellation of the city, using the population density as a density function. The same formulation can be generalized to other problems related to the optimal placement of resources, such a schools, distribution centers, mobile vendors, bus terminals, voting stations, service stops, etc.
--------------------------------------------------------------------------------
Cell division
There are many examples of animal and plant cells, usually monolayered or columnar, whose geometrical shapes are polygonal. In many cases, they can be indentified with a Voronoi tessellation and, indeed, with a centroidal Voronoi tessellation. Likewise, centroidal Voronoi tessellations can be used to model how cells are reshaped when they divide or when other cells are removed from a tissue. Here we consider one example, namely cell division in certain stages in the development of a starfish (Asterina pectinifera) embryo. During this stage, the cells are arranged in a hollow sphere consisting of a single layer of columnar cells. It has been observed that, viewed locally along the surface, the cells shapes closely match that of a Voronoi tessellation and, in fact, are that of a centroidal Voronoi tessellation.
The results of the cell division process can also be described using centroidal Voronoi tessellations. We start with a configuration of cells that, by observation, is a Voronoi tessellation. In this geometrical description of the cell shapes, cell division can be modeled as the addition of another Voronoi generator, or more precisely, as the splitting of a Voronoi generator into two generators. Having added a generator (or more than one if more than one cell divides), how does one determine the shapes of the new cells and the (necesarily) different shapes of the remaining old cells? It has been observed that the new shapes are very closely approximated by a centroidal Voronoi tessellation corresponding to the increased number of generators.
--------------------------------------------------------------------------------
Territorial behavior of animals
There are many species of animals that employ Voronoi tessellations to stake out territory. If the animals settle into a territory asynchronously, i.e., one or a few at a time, the distribution of Voronoi generators often resembles the centers of circles with fixed radius in a random circle packing problem. On the other hand, if the settling occurs synchronoulsy, i.e., all the animals settle at the same time, then the distribution of Voronoi centers can be that of a centroidal Voronoi tessellation.
As an example of synchronous settling for which the territories can be visualized, consider the mouthbreeder fish (Tilapia mossambica). Territorial males of this species excavate breeding pits in sandy bottoms by spitting sand away from the pit centers towards its neighbors. For a high enough density of fishes, this reciprocal spitting results in sand parapets which are visible territorial boundaries. After the fishes establish their territories, i.e., after the final position of the breeding pits are established, the parapets separating the territories have been observed to be polygonal and, in fact, can be very closely approximated by a centroidal Voronoi tessellation.
A behavioral model for how the fishes establish their territories can be described as follows. When the fishes enter a region, they first randomly select the centers of their breeding pits, i.e., the locations at which they will spit sand. Their desire to place the pit centers as far away as possible from their neighbors cause the fish to continuously adjust the position of the pit centers. This adjustment process is modeled as follows. The fishes tend to move their spitting location towards the centroid of their current territory; subsequently, the territorial boundaries must change since the fishes are spitting from different locations. Since all the fishes are assumed to be of equal strength, i.e., they all presumably have the same spitting ability, the new boundaries naturaly define a Voronoi tessellation of the sandy bottom with the pit centers as the generators. The adjustment process, i.e., movement to centroids and subsequent redefinition of boundaries, continues until a steady state configuration is achieved. The final configuration is a centroidal Voronoi tessellation.
--------------------------------------------------------------------------------
Algorithms
We have considered two iterative methods found in the literature for determining centroidal Voronoi tesselations. The first, known as Lloyd's method, is a deterministic, fixed point iteration; the second method, k-means, is a probabilistic method. Both methods begin with a choice for a density function, for the number n of suregions in the desired tessellation (or equivalently, the number of centroids), and given initial locations for the n points. The latter may be chosen, e.g., by a Monte Carlo method based on the given density function. The goal of both methods is to determine final locations for the n points so that these are the centroids, with respect to the given density function, of their corresponding Voronoi regions.
--------------------------------------------------------------------------------
Lloyd's method
Given a density function and an initial set of n points,
1. determine the Voronoi tesselation corresponding to the n points;
2. determine the centroids (with respect to the given density function) of the n Voronoi regions;
3. repeat steps 1 and 2 until satifactory convergence is achieved.
Lloyd's method may be viewed as a fixed point iteration for the mapping from the generating points to the associated Voronoi regions composed with the mapping from the Voronoi regions to their centroids. We have shown how to determine the derivatives of these mappings. We have also defined and "energy" whose minimum points are fixed points of the Lloyd map. We have studied Lloyd's method in the one-dimensional setting, giving a set of sufficient conditions for its convergence and showing that, in general, it is only linearly convergent.
--------------------------------------------------------------------------------
k-means
Given a density function and an initial set of n points,
1. select a point at random accoring to the given density function;
2. locate which of the n points is nearest to the new point;
3. proportionally average the new point and the point found in step 2; the old point should be weighted by the number of times it was previoulsy updated;
4. replace the point found in step 2 by the average found in step 3;
5. repeat steps 1 through 4 until satifactory convergence is achieved.
Note that the k-means method does not require the construction of the Voronoi diagrams during the iteration.
--------------------------------------------------------------------------------
Sample tessellations
Uniform density Voronoi tessellation for a Monte Carlo distribution of 256 points
Uniform density Voronoi tessellation for a centroidal Voronoi distribution of 256 points
Gaussian density Voronoi tessellation for a Monte Carlo distribution of 256 points
Gaussian density Voronoi tessellation for a centroidal Voronoi distribution of 256 points
Other sample tessellations may be found in the paper cited below.
--------------------------------------------------------------------------------
Paper
Centroidal Voronoi tessellations: applications and algorithms; to appear; Q. Du, V. Faber, and M. Gunzburger.
A centroidal Voronoi tessellation is a Voronoi tessellation of a given set such that the associated generating points are centroids (centers of mass) of the corresponding Voronoi regions. We give some applications of such tessellations to problems in image compression,quadrature rules, finite difference schemes, distribution of resources, cellular biology, and the territorial behavior of animals. Then, we discuss methods for computing these tessellations, provide some analyses concerning both the tessellations and the methods for their determination, and finally, present the results of some numerical experiments.
--------------------------------------------------------------------------------
Return to
Max Gunzburger home page
E-mail to Max Gunzburger
gunzburg@iastate.edu
--------------------------------------------------------------------------------
Last updated: 12/4/98 by Max Gunzburger
from that page: (Centroidal Voronoi Tessellations; territorial behavior of animals)
--------------------------------------------------------------------------------
Centroidal Voronoi Tessellations
--------------------------------------------------------------------------------
A centroidal Voronoi tessellation is a Voronoi tessellation of a given set such that the associated generating points are centroids (centers of mass with respect to a given density function) of the corresponding Voronoi regions. Such tessellations are useful, in among other contexts, in data compression, optimal quadrature rules, optimal representation and quantization, finite difference schemes, optimal distribution of resources, cellular biology, and the territorial behavior of animals. We have studied methods for computing these tessellations, provided some analyses concerning both the tessellations and the methods for their determination, and computed sample tessellations. Details may be found in the paper cited below.
--------------------------------------------------------------------------------
Return to
Max Gunzburger home page
E-mail to Max Gunzburger
gunzburg@iastate.edu
--------------------------------------------------------------------------------
Collaborators
Qiang Du -- Iowa State University and Hong Kong University of Science and Technology
Vance Faber -- Lizardtech, Inc.
--------------------------------------------------------------------------------
Applications
--------------------------------------------------------------------------------
Data compression
We will use a context from image processing; however, the basic ideas and principles are valid for many other data compression applications.
The setting is as follows. We have a color picture composed of many pixels, each of which has an associated color. Each of the colors is a combination of basic, e.g., primary, colors. In a given picture, there may be many different colors. For example, there may be on the order of a million pixels in a picture, with each pixel potentially having a different color. Our task is to approximate the picture by replacing the color at each pixel by one from a smaller set of colors. The natural questions are: how does one choose the smaller, approximating set of colors and how does on assign the colors in the original picture to the colors in approximating set? In a straightforward way, one may use a Monte Carlo method, using the distribution of colors (suitably normalized) as a probability density, to choose the set of approximating colors. Once this set is determined, it is natural to choose the assignment sets to be the associated Voronoi sets (in color space). Unfortunately, even with 256 approximating colors, the approximate pictures produced in this manner are not always satifactory. A better method for choosing the approximating colors is to construct a centroidal Voronoi tessellation of the color space. Then, the centroids of the Voronoi regions are chosen to be the approximating colors and the assignment sets are the corresponding Voronoi regions.
We provide a gray-scale example comparing compressed images found by a Monte Carlo method and by the centroidal Voronoi algorithm. Clearly, the latter is a better approximation of the original picture.
An 8-bit monochrome picture
The compressed 3-bit image by the Monte Carlo simulation
The compressed 3-bit image by the centroidal Voronoi algorithm
--------------------------------------------------------------------------------
Optimal quadrature rules
Consider piecewise constant quadrature rules. Here, we subdivide the region of integration into subregions and approximate the integral by the sum of the products of the volumes of the subregions and the integrand evaluated at a point in the subregion. The optimal error estimate for such a rule is achieved when the subregions are a centroidal Voronoi tessellation with the quadrature points chosen to be the centroids of the subregions. This result can be extended to composite one-point rules involving the evalution of derivatives of the functional.
--------------------------------------------------------------------------------
Optimal representation and quantization
Consider the representation or interpolation of observed data. For example, one of the earliest practical applications of Voronoi diagrams was to the problem of estimating the total precipitation over a period of time in a given geographical region. The best locations for the pluviometers in order to reduce the estimation error is at the centroids of a centroidal Voronoi tessellation of the geographic region. A similar example is the question of round-off, e.g., to represent real numbers by the closest integers. This optimal answer is obviously a simple example of one-dimensional centroidal Voronoi diagrams.
The representation of a given quantity with less information is often referred to as quantization and is an important subject in information theory. The subject of vector quantization has broad applications in signal processing and telecommunication. The image compression example we discussed earlier belongs to this subject as well.
--------------------------------------------------------------------------------
Finite difference schemes having optimal truncation errors
A common way to define finite difference schemes on irregular meshes for the approximate solution of partial differential equations is based on Voronoi tessellations and its dual tessellation, the Delaunay triangulation. In many cases, using centroidal Voronoi tesselations guarantee a second-order truncation error for the difference equations compared to a first-order truncation error for other Voronoi tesselations. Similar results are know for covolume methods based on the dual Voronoi-Delaunay tessellations.
--------------------------------------------------------------------------------
Optimal placement of resources
A typical example among problems dealing with the optimal placement of resources is the placement of mailboxes in a city or neighborhood so as to make them most convenient for users. Consider the following assumptions.
A user will use the mailbox nearest to their home.
The cost (to the user) of using a mailbox is a function of the distance from the user's home to the mailbox.
The total cost to users as a whole is measured by the distance to the neareast mailbox averaged over all users in the region.
The optimal placement of mailboxes is defined to be the one that minimizes the total cost to the users.
Then, it is not difficult to show that the optimal placement of the mailboxes is at the centroids of a centroidal Voronoi tessellation of the city, using the population density as a density function. The same formulation can be generalized to other problems related to the optimal placement of resources, such a schools, distribution centers, mobile vendors, bus terminals, voting stations, service stops, etc.
--------------------------------------------------------------------------------
Cell division
There are many examples of animal and plant cells, usually monolayered or columnar, whose geometrical shapes are polygonal. In many cases, they can be indentified with a Voronoi tessellation and, indeed, with a centroidal Voronoi tessellation. Likewise, centroidal Voronoi tessellations can be used to model how cells are reshaped when they divide or when other cells are removed from a tissue. Here we consider one example, namely cell division in certain stages in the development of a starfish (Asterina pectinifera) embryo. During this stage, the cells are arranged in a hollow sphere consisting of a single layer of columnar cells. It has been observed that, viewed locally along the surface, the cells shapes closely match that of a Voronoi tessellation and, in fact, are that of a centroidal Voronoi tessellation.
The results of the cell division process can also be described using centroidal Voronoi tessellations. We start with a configuration of cells that, by observation, is a Voronoi tessellation. In this geometrical description of the cell shapes, cell division can be modeled as the addition of another Voronoi generator, or more precisely, as the splitting of a Voronoi generator into two generators. Having added a generator (or more than one if more than one cell divides), how does one determine the shapes of the new cells and the (necesarily) different shapes of the remaining old cells? It has been observed that the new shapes are very closely approximated by a centroidal Voronoi tessellation corresponding to the increased number of generators.
--------------------------------------------------------------------------------
Territorial behavior of animals
There are many species of animals that employ Voronoi tessellations to stake out territory. If the animals settle into a territory asynchronously, i.e., one or a few at a time, the distribution of Voronoi generators often resembles the centers of circles with fixed radius in a random circle packing problem. On the other hand, if the settling occurs synchronoulsy, i.e., all the animals settle at the same time, then the distribution of Voronoi centers can be that of a centroidal Voronoi tessellation.
As an example of synchronous settling for which the territories can be visualized, consider the mouthbreeder fish (Tilapia mossambica). Territorial males of this species excavate breeding pits in sandy bottoms by spitting sand away from the pit centers towards its neighbors. For a high enough density of fishes, this reciprocal spitting results in sand parapets which are visible territorial boundaries. After the fishes establish their territories, i.e., after the final position of the breeding pits are established, the parapets separating the territories have been observed to be polygonal and, in fact, can be very closely approximated by a centroidal Voronoi tessellation.
A behavioral model for how the fishes establish their territories can be described as follows. When the fishes enter a region, they first randomly select the centers of their breeding pits, i.e., the locations at which they will spit sand. Their desire to place the pit centers as far away as possible from their neighbors cause the fish to continuously adjust the position of the pit centers. This adjustment process is modeled as follows. The fishes tend to move their spitting location towards the centroid of their current territory; subsequently, the territorial boundaries must change since the fishes are spitting from different locations. Since all the fishes are assumed to be of equal strength, i.e., they all presumably have the same spitting ability, the new boundaries naturaly define a Voronoi tessellation of the sandy bottom with the pit centers as the generators. The adjustment process, i.e., movement to centroids and subsequent redefinition of boundaries, continues until a steady state configuration is achieved. The final configuration is a centroidal Voronoi tessellation.
--------------------------------------------------------------------------------
Algorithms
We have considered two iterative methods found in the literature for determining centroidal Voronoi tesselations. The first, known as Lloyd's method, is a deterministic, fixed point iteration; the second method, k-means, is a probabilistic method. Both methods begin with a choice for a density function, for the number n of suregions in the desired tessellation (or equivalently, the number of centroids), and given initial locations for the n points. The latter may be chosen, e.g., by a Monte Carlo method based on the given density function. The goal of both methods is to determine final locations for the n points so that these are the centroids, with respect to the given density function, of their corresponding Voronoi regions.
--------------------------------------------------------------------------------
Lloyd's method
Given a density function and an initial set of n points,
1. determine the Voronoi tesselation corresponding to the n points;
2. determine the centroids (with respect to the given density function) of the n Voronoi regions;
3. repeat steps 1 and 2 until satifactory convergence is achieved.
Lloyd's method may be viewed as a fixed point iteration for the mapping from the generating points to the associated Voronoi regions composed with the mapping from the Voronoi regions to their centroids. We have shown how to determine the derivatives of these mappings. We have also defined and "energy" whose minimum points are fixed points of the Lloyd map. We have studied Lloyd's method in the one-dimensional setting, giving a set of sufficient conditions for its convergence and showing that, in general, it is only linearly convergent.
--------------------------------------------------------------------------------
k-means
Given a density function and an initial set of n points,
1. select a point at random accoring to the given density function;
2. locate which of the n points is nearest to the new point;
3. proportionally average the new point and the point found in step 2; the old point should be weighted by the number of times it was previoulsy updated;
4. replace the point found in step 2 by the average found in step 3;
5. repeat steps 1 through 4 until satifactory convergence is achieved.
Note that the k-means method does not require the construction of the Voronoi diagrams during the iteration.
--------------------------------------------------------------------------------
Sample tessellations
Uniform density Voronoi tessellation for a Monte Carlo distribution of 256 points
Uniform density Voronoi tessellation for a centroidal Voronoi distribution of 256 points
Gaussian density Voronoi tessellation for a Monte Carlo distribution of 256 points
Gaussian density Voronoi tessellation for a centroidal Voronoi distribution of 256 points
Other sample tessellations may be found in the paper cited below.
--------------------------------------------------------------------------------
Paper
Centroidal Voronoi tessellations: applications and algorithms; to appear; Q. Du, V. Faber, and M. Gunzburger.
A centroidal Voronoi tessellation is a Voronoi tessellation of a given set such that the associated generating points are centroids (centers of mass) of the corresponding Voronoi regions. We give some applications of such tessellations to problems in image compression,quadrature rules, finite difference schemes, distribution of resources, cellular biology, and the territorial behavior of animals. Then, we discuss methods for computing these tessellations, provide some analyses concerning both the tessellations and the methods for their determination, and finally, present the results of some numerical experiments.
--------------------------------------------------------------------------------
Return to
Max Gunzburger home page
E-mail to Max Gunzburger
gunzburg@iastate.edu
--------------------------------------------------------------------------------
Last updated: 12/4/98 by Max Gunzburger
posted by choesnah at 8/25/2003 08:25:00 pm
<< Home