The problem: These activities address the notion of "proximity", in that a set of points in the
plane is associated with "service regions" or "areas of influence." The plane is divided into
regions, one containing each point, such that every region consists of the area of the plane closest
to that point than any other. The completed division of the plane is referred to as a Voronoi
diagram, and the boundaries between the regions are called Voronoi edges. The purpose of these
activities is for students to develop a basic understanding of Voronoi diagrams, how they can be
constructed, and some current as well as possible applications.
Suggested materials: Handouts 1-5 in sequence, ruler/straightedge, compass, pencil (to allow for erasing.)
Prerequisites: ability to set up and solve a linear equation (experience with geometric terms such as "midpoint" and "bisect" are helpful, as is the construction of the perpendicular bisector of a segment, but these can also be taught as part of the activities.)
Guided Exploration: This series of activities is designed to constitute a guided exploration and as such, notes are included for each activity. Activities 1 and 2 can be completed in one period, with the writing assignment for Activity 2 as homework. Activity 3 with its writing assignment should take about one period, as should Activity 4, using Activity 5 as a closing assignment for the third day. Student work from Activity 5 can be used for assessment (and display!) purposes.
Activity 1: Students should be permitted to figure this out any way they wish. Only provide drawing tools as requested. Be sure to encourage students to be as accurate as possible. With luck, the boundary designed will be (close to) the perpendicular bisector of the segment which connects the two points (vertices.) Do not under any circumstances reveal in advance the term "perpendicular bisector" or discuss the construction of same at this point. Students should be permitted to complete the writing assignment for Activity 1 before proceeding. This should be accomplished immediately following the solving of the problem; students should share the results of the writing assignment with the class. From this, encourage the development of the notion of perpendicular bisector; if necessary, teach the construction procedure at this point, but definitely before going to Activity 2. Note: although it may be beneficial to actually draw in the segment connnecting the vertices in order to construct the perpendicular bisector, students should be advised to make sure it is erased immediately afterward, as it detracts from the neatness of the problem solution, and makes a mess of the diagram. This issue arises again in Activity 4.
Activity 2: At this point the students should be able to construct a perpendicular bisector between two vertices and understand how that construction solves the problem in Activity 1. Activity 2 asks the student to extend this notion to three vertices. It is vital in Activity 2 that students do the construction accurately and neatly, because the writing assignment for this activity notes that the three boundaries intersect at a common point, called a Voronoi vertex. If the construction is sloppy, this will not happen. The significance of this point is that it represents the unique location which is equidistant from all three vertices. It also represents the center of a circle which would include all three vertices on its surface. This in turn opens up a whole new possibility for extension problems, called "greatest empty circle" problems (see below for extensions and further activities.) Upon the conclusion of this activity, it is time to tell the students that the vertices together with the edges (boundaries) constitute a Voronoi Diagram. The boundaries are called Voronoi edges.
Activity 3: This one is a little more tricky and students may need some help getting started. Start them off by using each vertex (nucleation site) as the center of a set of concentric circles, each one .5" larger in radius than the previous, starting with a .5" radius circle. This circle represents the growth of the crystal in one time unit. As the circles grow, they begin to intersect, having two distinct intersection points. As before, this is enough to draw the perpendicular bisector for the two vertices. In reality, this bisector represents a straight boundary between two crystals that are trying to grow in a circular form. By drawing all the circles, it is possible to see how the growth pattern evolves over time. Do not point out that the intersections of these circles are equivalent to making the arcs during construction of a perpendicular bisector. Allow this to become self evident by the end of the exploration. In fact, a good sample student response to the writing assignment would indicate that simply constructing the perpendicular bisectors will save drawing all the circles, as the final result is the same.
Activity 4: This is a similar construction to Activity 3, but now the boundaries are permitted to grow at different rates. There is no special way to direct the students' construction, except to reinforce the importance of accuracy. With a larger number of vertices, the construction can get quite messy and confusing, which prompts the writing assignment for this activity. After allowing time for students to reflect on and respond to the writing assignment, solicit responses which lead into the following union of algebra and geometry to solve the problem. Use discretion in combining discovery with direct instruction to arrive at this solution method:
1. Draw and carefully measure the segment between a pair of vertices (call this 'd');
2. Let 't' = the number of time intervals for the growing circles to intersect;
3. Write an equation to find the value of 't' using one of the three possible situations:
a. .5t + .5t = d (two adjacent small fish) or
b. .5t + t = d (adjacent fish of different size) or
c. t + t = d (two adjacent large fish);
4. Use the solution from the appropriate equation to locate the distance from one of the
vertices where the parapets will meet, and mark this point on the segment connecting
the vertices;
5. Construct a perpendicular to the segment connecting the original vertices(call it AB)
through this point (call it P):
a. On segment AB, use a compass to mark two points equidistant from P (call them C and D),
b. From points C and D, use a compass and arcs to locate a new point Q on one side of AB, equidistant from C and D,
c. Construct the line containing P and Q, which is perpendicular to AB, and represents the Voronoi edge between A and B.
d. Erase segment AB and all construction marks;
6. Repeat this process with all other appropriate pairs of vertices.
Concluding the exploration: The exploration concludes with Activity 5, which also serves as the assessment component of this lesson. By now the students have had a chance to experience and discuss various types of problems which have a Voronoi diagram as the solution. At the teacher's discretion, students can work alone or in pairs to design and solve their own and each others' problems.
Extensions and further activities: Students should be encouraged to look out for new and different situations for which a Voronoi diagram would provide useful information. As a major extension, consider the "greatest empty circle" problem, locating a new point such that its minimum distance from any of the existing points is a maximum, such as a restaurant chain which wishes to open a new outlet as far away as possible from the competition, but not outside of the region. By measuring the distance between Voronoi vertices (those formed by the intersection of Voronoi edges) and the original vertices, it is possible to identify the Voronoi vertex which is the furthest from any original vertex, and which can be illustrated as the radius of a circle. By way of example, consider again Activity 4. Suppose a "new guy" comes on the scene and wishes to locate his breeding pit so as to allow him the maximum possible space. Locating the center of his breeding pit at the Voronoi vertex which has the greatest distance (maximum radius) from the other breeding pits.
Comments from teachers: "These activities proceed in a natural, logical fashion. Students of differing abilities may require different amounts of prompting and guidance to assist the 'discovery' nature of the unit." "I used this unit with above-average ninth graders, and was only disappointed to find how many of them were unable to use a compass and straightedge well, as well as having no prior experience with constructions." "Some of the students balked when they got to the activity about the crystals because they were intimidated by the scientific context. They needed to be convinced that the context of the problem didn't make it any more difficult to understand the solution. For some reason the scientific name of the mouthbreeder fish didn't bother them at all."
Comments from students: " I enjoyed solving these problems but had a hard time drawing the boundaries. Students need to be really careful that they measure and draw carefully and accurately." "I had a hard time trying to make up my own problem. The one I made up turned out to be what my teacher call a 'greatest empty circle' problem, which has interesting connections to the other problems we solved." "I was surprised to learn that problems that seem so different when I first saw them were solved the same way. I never would have thought of writing an equation on my own in the problem about the fish to find the boundary, but it makes sense, and does make the problem easier to solve."
References:
Dickerson, Matthew, and Drysdale, Scot; Voronoi Diagrams and Proximity Problems; COMAP; Lexington, MA; 1996.
Drysdale, Scot; lecture notes from DREI (Dimacs Research and Education Institute); 1996.
Okabe, Atsuyuki, et al; Spatial Tesselations: Concepts and Applications of Voronoi Diagrams;
John Wiley & Sons; New York, New York; 1992.