Project C08 - Voronoi Diagrams Project C08 - Voronoi Diagrams
A Voronoi diagram is a collection of polygons (regions) generated by a set of points (sites) such that any point inside one of the regions is closer to that region's site than to any other site. While the definition sounds pretty complicated, you are probably familiar with these diagrams - they arise in many situations.
  1. It is very easy to construct a Voronoi diagram generated by two sites-simply construct the perpendicular bisector of the line segment joining the sites. Use a compass and a straight-edge to construct the Voronoi diagram generated by the two sites shown below.

  2. It is a little bit tougher to construct a Voronoi diagram generated by three sites. You should start by constructing the perpendicular bisectors of the three line segments joining pairs of points. Then erase the unwanted portions of the lines to form the three regions. It sounds difficult, but try it.
    1. Use a compass and a straight-edge to construct the Voronoi diagram generated by the sites shown below.

    2. Suppose that the three sites correspond to three cities. These cities have decided to cooperate and build one landfill that will service them all. The landfill will be constructed somewhere within the limits of the three cities (inside the big polygon). Unfortunately, none of the cities wants the landfill on its land, and neighboring communities want it as far away as possible. Use your Voronoi diagram to determine the most reasonable location(s) for the landfill.
  3. The following data were collected from several locations in Jackson County. A map of Jackson county (1 cm:10 mi) is shown below.

    Location April Rainfall
    A 8.2 in
    B 7.3 in
    C 6.7 in
    D 4.2 in
    E 5.5 in
    F 7.9 in

    1. Use a compass and a straight-edge to draw the corresponding Voronoi diagram.
    2. Approximate the actual area of each of the six regions. (Hint: One easy, but tedious, way to do this is to split each polygonal region into triangles and use Heron's formula1 to find the area of each triangle. Click here to use Heron's formula online.)
    3. Based on the areas of the regions and the data in the table, compute a weighted average that gives an estimate for the average April rainfall in Jackson county.
  4. Voronoi diagrams arise in many applications.
    1. Explain how Voronoi diagrams might be used map out the territories of wild animals.
    2. Suppose that four dots represent the locations on a map of the dens of four grizzly bears. Draw a rough sketch of the corresponding Voronoi diagram. (This time don't use a compass and a straight-edge, just do your best working freehand.)

  5. Find at least two other applications of Voronoi diagrams.

Footnotes:

1 A triangle with side lengths a, b, and c has area [(s(s-a)(s-b)(s-c))]1/2, where s = 1/2(a+b+c).

File translated from TEX by TTH, version 1.98.
On 13 Oct 2000, 09:37.