E-mail to Max Gunzburger
Collaborators
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.
- 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