CVT_METRIC
CVT Calculation With Varying Metric


CVT_METRIC is a MATLAB program which computes a CVT (Centroidal Voronoi Tessellation) calculation under a spatially varying metric.

What we are saying is that the distance between two vectors a and b is no longer simply the Euclidean distance, but rather a quadratic form involving a spatially varying, positive definite symmetric matrix that represents the metric:


        d(a,b) = ( a - b )' * A * ( a - b )
      
We assume that A varies spatially, but we would prefer to simplify this variation in a manner that saves us computational effort, while allowing us to recover the variational behavior if we are willing to use a finer spatial sampling.

The metric function is distinct from the density function, which can also be used in these kinds of problems. The density function is weaker, and corresponds to a metric whose matrix at any point is a multiple of the identity matrix. A density function approach cannot result in the more interesting anisotropic effects that an arbitrary metric produces.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

CVT_METRIC is available in a MATLAB version.

Related Data and Programs:

CVT_1D_LLOYD, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density.

CVT_1D_NONUNIFORM, a MATLAB library which allows the user to watch the evolution of a CVT computed over a 1D interval with a nonuniform density.

CVT_2D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit square [0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

CVT_DEMO, a MATLAB library which allows the user to generate a CVT over several geometric regions using uniform or nonuniform density.

CVTM_1D, a MATLAB program which estimates a mirror-periodic centroidal Voronoi Tessellation (CVTM) in the periodic interval [0,1], using a version of Lloyd's iteration.

CVTP_1D, a MATLAB program which estimates a periodic centroidal Voronoi Tessellation (CVTP) in the periodic interval [0,1], using a version of Lloyd's iteration.

FLORIDA_CVT_GEO, MATLAB programs which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.

LCVT, a MATLAB library which computes a "Latinized" Centroidal Voronoi Tessellation.

TEST_TRIANGULATION, a MATLAB library which defines the geometry of a number of sample regions.

Reference:

  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, Number 3, pages 345-405, September 1991.
  2. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review, Volume 41, 1999, pages 637-676.

Source Code:

Examples and Tests:

The following files contain functions to evaluate various simple metrics:

Here are images of CVT point sets. These are crude calculations, with a relatively low number of sample points and iterations. This is partly because I haven't figured out how to optimize these calculations in MATLAB.

You can go up one level to the MATLAB source codes.


Last revised on 25 May 2006.