Sampling Milestone

In the Voronoi milestone and notebook, we looked at situations in which we needed to compute the area, centroid, and "energy" associated with each Voronoi polygon. Remember that we are assuming that we restrict the Voronoi diagram to a finite portion of the infinite line or plane. In the 1D case, the calculations seem easy; in the 2D case, all the polygons are still polygons if our restricted region is a square (or any polygon); however, if our restricted region was a circle, then even computing the area of a subregion could be difficult.

We saw in the Voronoi notebook how we could replace exact computations by approximations using uniform sampling. For an example restricted to a square, we were able to compare the exact and approximate calculations and saw that they were close.

Now we are going to look at approximate calculations for some other 2D shapes. The main idea will be the same; the major difference will be that, although it was easy to come up with a way to uniformly sample a square, we have to be more careful when the restricted region is a triangle, polygon, circle or some other shape.

For now, we are only interested in uniform sampling; that is, every point in the restricted region should have an equal chance of being selected. Later, we will find that it is sometimes useful to allow some points to be more selectable than others.

Topics:

• Review uniform sampling for the unit square from the Voronoi notebook.
• Extend uniform sampling to any rectangle, cube, or hypercube, with sides aligned with coordinate directions.
• Review uniform sampling for any triangle, from the triangles notebook.
• Consider uniform sampling of a line divided into unequal lengths;
• Extend uniform sampling to any (simple) polygon.
• Introduce uniform sampling for a circle.