The CVT Census Milestone

http://people.sc.fsu.edu/~jburkardt/classes/urop_2016/cvt_census_milestone.html

After a great deal of work and preparation, we know enough to look at an interesting practical problem, the application of the ideas of Centroidal Voronoi Tessellations to the problem of subdividing a political territory into voting districts of approximately equal population and "reasonable" shape.

The actual ideas we need to use depend on the kind of data we have available. We plan to look at the state of Florida, and we have already seen that we had to compromise when representing the geometry of Florida by defining it as the inside of a polygon with a few hundred sides. One effect of this compromise is that we need to pretend that Key West doesn't exist. Moreover, we will see that a number of other small bits of Florida are not actually inside our polygon.

Congressional districts are allocated in such a way that they have roughly equal population. That means that we want to use population as a sort of density function. The exact way we do this depends on how the population density is made available to us.

The United States Census Bureau stores a great deal of information that can help us in this task. The first thing to realize, though, is that we will not have a true population density function, but rather a sort of discrete representation, in which the state has been broken down into very small units, on the order of city blocks, in which the total population is given. The data will be a list of locations, populations, and a single longitude and latitude. Therefore, the population information is actually given as a list of discrete data points. So we will have to adjust our CVT approach to deal with a polygonal region containing a list of population points.

Topics we will need to learn include:

• Reading in the file containing the populations and locations (this will be the file "florida_census.txt" available on this web page.)
• setting up the PDF and CDF structures that will allow us to uniformly sample a single person from the population.
• setting up a scheme to randomly sample N persons from the population, along with their locations.
• Initializing a location for the ``generator'' of each of the 27 congressional districts.
• computing the nearest congressional generator to each randomly sampled point.
• setting up a CVT iteration that takes N samples, computes nearest generators, and then replaces each generator by the centroid of the sampled populations.