CVT Florida Milestone

We have practiced estimating the CVT of a set of points in a polygon. But the problem becomes more interesting, and a little harder, when we look at data from a real life application. Let's see what happens if we ask how to compute a CVT of Florida.

We begin by realizing that Florida is a very complicated object, so we are going to need to agree on a model of Florida, that is, some idealized, simplified, mathematical or computational object whose relationship to Florida is clear, but which can "fit" into our minds, or our computers.

We can think about Florida as a shape on a map. Although that shape is quite complicated, we will be satisfied if it is approximated by a polygon that looks like Florida to us. Since Florida is a patch on the surface of a globe (of course, this is also only a model of reality!), any point can be described by a longitude and latitude measurement. So we can hope to get a description of a polygon for the shape of Florida, in terms of a sequence of longitudes and latitudes.

Another approximation we will make is that we will "flatten" Florida. We will treat the longitude and latitude as X and Y coordinates, and draw pictures and measure distances as though Florida were a planar object.

Once we have a polygon that models Florida, we can ask for a CVT by scattering a few random generators in the interior. In fact, it might be better if we choose the longitudes and latitudes of a few recognizable Florida cities as our starting generator locations. Once we have a polygon and some generators, we can let our CVT iteration run.

Note that our result will be a CVT that divides up Florida according to geography, but which has no idea about population density. So the size of the districts it chooses will be roughly the same... in geographic area, but not in population. We will have to work harder, later, to be able to include population in our computations.

Topics:

• We need a polygon describing Florida. A text file is available called "florida.shape.txt". We need to read this file and make a plot to convince ourselves that we've got what we need.
• We need the location of some Florida cities to use as initial generators.
• We talked earlier about how to sample a polygon, and how to determine if a point was inside a polygon. We suggested that one way to do this was to triangulate the polygon, and then work with the triangles. But because the Florida polygon has hundreds of vertices, we will look at what may be faster and better methods of sampling and determining point inclusion.
• We will build a number of functions, and then put them together to make a procedure that computes the CVT of Florida. We expect that a plot of the final result will convince us of the correctness of our approach.