VORONOI DIAGRAMS: Which district school is closest to your home?

Marylu Tyndell (tyndell@worldnet.att.net)

General Information

The Problem

Recently, school transportation in NJ had become an issue. The voters in each district were being given the opportunity to decide whether hazardous busing should be included in the school budget. "Hazardous busing" is considered to be the busing of students who live within a 1.5 mile radius of their elementary school and whose walk to school would be along a dangerous route, i.e., major highways, roads without sidewalks, etc. If the majority of the voters chose not to include this hazardous busing, the students would be forced to walk to school or to provide their own transportation.

The problem, therefore, would be to maximize the number of students who would have to walk to the schools and to minimize the walks for the students in the hazardous busing category. In other words, separate the sending districts into school zones according to a Voronoi diagram, where all homes in each school zone are closer to the school in that zone than any other school in the district.

Suggested Materials

Map of the school district

color pencils

color markers

rulers *

protractors *

* (can also be done by compass and straightedge construction)

Prerequisites

Knowledge of perpendicular bisectors and equidistance.

Activity Description

Guided Exploration

A. Use the map of your town to mark the current location of the elementary schools. Mark each school with a different color marker.

B. Draw segments between relevant pairs of schools. Construct the perpendicular bisectors for the segments. (Leave the perpendicular bisectors, but erase the segments.)

C. Identify the parts of the perpendicular bisectors that form the regions that each contain one school. The parts of the perpendicular bisector which you keep are the points closer to A or B than to any other point.

D. Have each student in your group mark the location of his/her home with color pencil.

This is a VORONOI DIAGRAM.

1. What do these regions represent in relation to the schools?

2. Which school would you go to from your home? Why? Does the Voronoi diagram support your answer?

3. Why might developers and planners be interested in this Voronoi diagram?

4. Compare these regions with those used for the schools in real-life. What would prevent the town from using your Voronoi diagram for the school district?

Sample Results from Exploration

During the course of this lesson, I decided to get a large-scale view of the results for the district by compiling student information on one map. With three geometry classes participating, we located approximately 75 student homes on the map. We denoted each student's home with a colored pencil ( the color matching the elementary school to which they would be assigned). The completed map showed each elementary school and all the students' homes in color. Using this map, we could easily locate those students whose homes did not "fit" properly into the Voronoi diagram. This map was the reference for most of the follow-up questions.

A Mathematical Approach

The perpendicular bisector of a segment is the line that bisects and is perpendicular to the segment. The points on the perpendicular bisector (p.b.) are equidistant from the endpoints of segment. So, any points which are not on the p.b. are closer to one endpoint than the other. All the points that are closer to that site than any other would be in that site's region in a Voronoi diagram.

In a Voronoi diagram, there may be many sites. Constructing the perpendicular bisector between each pair of sites will separate an area into regions. Each point in each region will be closer to the site in that region than to any other site in the diagram.

Further Problems for Review or Assessment

For different problem contexts, have the students consider the service areas for one of the following situations: firehouses, first aid stations, election polling places, video stores, pizza, parlors, hardware stores, etc.

Writing Assignment

Have the students write instructions on how to create a Voronoi diagram given 3 points as sites.

Followup Problems or Activities

1. If the district were to build a new elementary school, where would you suggest that the best site would be? Show your suggested site on the map and explain how this decision was made.

2. Create a Voronoi diagram for the fire stations in town. Look over the map and see if you can find any area of town where using the diagram would be a disadvantage. Show that area of the map and explain your answer in detail.

Teaching Notes

References

1. Drysdale, Scot, Workshop on Voronoi Diagrams, Princeton University, July 1996.

2. Rhoad, Milauskas,and Whipple,Geometry for Enjoyment and Challenge. McDougal, Littell & Co.,Chicago ,IL ,1991.

3. Dickerson, Matthew, and Drysdale, Scot; Voronoi Diagrams and Proximity Problems; COMAP; Lexington, MA;1996