# usa_cvt_geo

usa_cvt_geo, MATLAB codes which explore the creation of a centroidal Voronoi Tessellation (CVT) of the continental United States, based solely on geometric considerations.

The main data item needed is a list of the longitudes and latitudes of points that form a polygon that approximates the boundary of the United States. Having such a polygon makes it possible to draw points uniformly at random from the interior of the US. This makes it possible to estimate computationally the value of certain geometric data including area, centroids, and the centroidal Voronoi Tessellation.

The function usa_sample_geo() can return a set of points drawn uniformly at random from the interior of the US.

Using the border polygon definition, usa_point_display() can display a set of points representing locations in the US, specified by their longitude and latitude.

Given a set of points in the US, usa_voronoi_display() can show the resulting Voronoi diagram. Note that, because of shortcomings in MATLAB's voronoi() command, some tricks had to be used to get a satisfactory plot. In particular, because rays to infinity are not returned, an auxilliary frame of points was added around the boundary, which fixes that problem, while causing the display of somewhat spurious cell boundary lines well outside of the region of interest.

Given a set of points in the US, usa_centroid_geo() can estimate the centroids of the "in-USA" Voronoi cells.

The function usa_cvt_geo() can estimate the location of generator points corresponding to a centroidal Voronoi tessellation of the geometric information in the US.

### Languages:

usa_cvt_geo is available in a MATLAB version.

### Related Data and Programs:

cvt_box, a MATLAB code which constructs a modified CVT in which some points are forced to lie on the boundary.

ccvt_reflect, a MATLAB code which tries to construct a modified CVT in which some points are forced to lie on the boundary, using a reflection idea.

cvt, a dataset directory which contains a variety of examples of CVT datasets.

cvt_1d_nonuniform, a MATLAB code which constructs a CVT in one dimension, under a nonuniform density function.

cvt_1d_sampling, a MATLAB code which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using sampling to estimate the Voronoi regions.

cvt_2d_sampling, a MATLAB code 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_3d_sampling, a MATLAB code which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit cube [0,1]x[0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

cvt_circle_nonuniform, a MATLAB code which calculates a nonuniform Centroidal Voronoi Tessellation (CVT) over a circle.

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

cvt_corn, a MATLAB code which studies a 2D model of the growth of a corn kernel, by treating the surface and interior biological cells as points to be organized by a Centroidal Voronoi Tessellation (CVT) with a nonuniform density; during a sequence of growth steps, new biological cells are randomly added to the surface and interior.

cvt_ellipse_uniform, a MATLAB code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over an ellipse, with a uniform density.

cvt_1_movie, a MATLAB code which creates an animation of the evolution of a Centroidal Voronoi Tessellation (CVT);

cvt_2_movie, a MATLAB code which creates a Centroidal Voronoi Tessellation (CVT) movie;

cvt_3_movie, a MATLAB code which creates a Centroidal Voronoi Tessellation (CVT) movie in a region of unusual shape;

cvt_4_movie, a MATLAB code which creates a Centroidal Voronoi Tessellation (CVT) movie in a square, with a density function that drives points to the corners;

cvt_square_pdf_discrete, a MATLAB code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a density derived from a discrete PDF.

cvt_square_uniform, a MATLAB code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a uniform density.

cvt_triangle_uniform, a MATLAB code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a triangle, with a uniform density.

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

florida_cvt_pop, MATLAB codes which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based on population density.

line_cvt_lloyd, a MATLAB code which applies Lloyd's iteration repeatedly to a set of N points, to compute a Centroidal Voronoi Tessellation (CVT) over the interior of a line segment in 1D.

matlab_map, MATLAB codes which illustrate the use of the MATLAB Mapping Toolbox.

sphere_cvt, a MATLAB code which uses a Centroidal Voronoi Tessellation to create a mesh of well-separated points on the surface of the unit sphere in 3D.

usa_box_plot, a MATLAB code which can create simplified maps of the USA in which each state appears as a box, and the placement of the boxes only roughly corresponds to the relative locations of states on an accurate map.

### Reference:

1. Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review,
Volume 41, Number 4, December 1999, pages 637-676.
2. Lili Ju, Qiang Du, Max Gunzburger,
Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
Parallel Computing,
Volume 28, 2002, pages 1477-1500.
3. The Mathworks,
Mapping Toolbox User's Guide, R2016a.

### Source Code:

Last revised on 13 January 2021.