Voronoi Milestone

The Voronoi diagram is an important topic in computational geometry. We are given a set of points which we'll call generators. These points may lie in a 1-dimensional space (the entire line or a line segment); most often we are interested in some 2-dimensional space, the whole plane, or a square, circle, or polygonal region. We will see later that the concept of a Voronoi diagram extends to the 3D case and higher dimensions.

The Voronoi diagram is a subdivision of the original space. Every point is assigned to the nearest generator. In a 1-D problem, this divides the line into subintervals; in a 2-D problem, this divides the plane into polygons, some of which will be infinite. We are often interested in only a finite subregion of the plane. In such cases, we can simply imagine looking at a plot of the Voronoi diagram on the infinite plane, drawing a line that marks the border of our finite region, and throwing the rest away. If our border line has straight sides, then all our Voronoi subregions will be polygonal. If the border is curved, then the Voronoi subregions that touch the border will include a curved segment.

Topics:

• The exact 1D Voronoi diagram for the whole line:
  • What is the Voronoi diagram of the 4 points G4 = {1/5, 2/5, ..., 4/5}?
• The exact 1D Voronoi diagram for the segment [0,1]:
  • What is the Voronoi diagram of G4 now? Describe each Voronoi "polygon" as an interval pi = [ai,bi].
  • What are the centroids c1, c2, c3, c4 of the Voronoi "polygons"?
  • What are the lengths l1, l2, l3, l4 of the Voronoi "polygons"?
  • The Voronoi polygon pi associated with gi in G4 has an "energy" ei, which is the integral ei=Int(gi)(x-gi)^2dx. What are the values of e1, e2, e3 and e4?
  • How would e1 change if we moved p1 (the point 1/5) to the centroid c1 of the interval [a1,b1], but didn't change anything else?
• The approximate 1D Voronoi diagram for the segment [0,1]:
  • Assume we have the same set G4 of generator points. Instead of calculating things directly, we will estimate them using sample points. Suppose we generate 1000 random value in [0,1].
  • We know the whole line segment has length 1. Estimate the length li of each Voronoi polygon by counting the number of sample points that are closest to gi, and multiplying that by 1/1000 times the length of [0,1]. Compare your estimates to the exact values.
  • Estimate each centroid ci by averaging all the sample points that are closest to gi. Compare your estimates to your exact values.
  • Estimate the energy ei by averaging the value (x-gi)^2 for all sample points closes to gi, and multiplying by your estimated interval length. Compare your estimates to your exact values.
  • We conclude from this exercise that we can approximate the size, centroid, and energy of each 1D Voronoi polygon by using random sampling.
• The exact 2D Voronoi diagram:
  • In 2D, we can generate a regular grid by starting with G4={1/5,2/5,3/5,4/5} and taking a tensor product. In Python, this is done with the "X,Y=numpy.meshgrid(G4,G4)" function.
  • On a piece of paper, sketch the position of these 16 points and your guess as to the shape of the Voronoi diagram.
  • Use the scipy.spatial.Voronoi(X,Y) function to draw the actual Voronoi diagram. Notice that some Voronoi polygons are finite, but some are infinite. Infinite polygons will have infinite area, centroids, and energy.
  • Suppose we are only interested in points within the unit square [0,1]x[0,1]. This means we simply ignore everything outside the square. Convince yourself that the Voronoi polygons are now all finite. Moreover, they are all polygonal.
  • Suppose we are only interested in points within the unit circle (x-0.5)^2 + (y-0.5)^2 = 0.5. Convince yourself that the Voronoi polygons are all finite, but some of them no longer are polygonal!
• The approximate 2D Voronoi diagram for the unit square [0,1]x[0,1]:
  • Suppose we are using the same set of 16 points as discussed above, and restrict our data to the unit square. Instead of doing exact arithmetic, we will generate N=10,000 random sample points in the unit square, using numpy.random.rand(10000,2).
  • Estimate the area a1 of polygon p1 by counting the counting the number of sample points closest to g1, and multiplying by the area of the unit square divided by N.
  • Estimate the centroid c1 of polygon p1 by averaging the sample points that are closest to g1.
  • Estimate the energy e1 of polygon p1 by summing (x-g1)^2 over the sample points closest to g1, and multiplying by a1, your estimate for the area.
• The approximate 2D Voronoi diagram for any finite region:
  • We can estimate the area, centroid, and energy of each Voronoi region using sampling. The quality of the estimate improves with the number of sample points. Our calculation is just as easy for cases where the region is not polygonal (but still finite!), as long as we have a way to generate uniform sample points in that region. (To handle the case where the region is a circle, we have to come up with a way to sample the circle uniformly, for instance.)