The Voronoi Diagram Package


The following material describes the first software package I plan to develop as part of Teaching Geometry through Geography: A Computer Approach.

Background on the Voronoi Diagram

The Voronoi diagram is a simple mathematical construct that has proved useful in fields as diverse as environmental studies, cell biology, crystallography, transportation planning, and communications theory. Due to its many practical applications, it has been much studied in the past decade by practitioners of computational geometry, a branch of computer science.

A Voronoi diagram may be generated by any finite set of points in a plane. Imagine the plane is a map of a city, and the points are polling places. Imagine election law requires that each citizen vote at the polling place which is closest to their home (as the crow flies). Then the resulting election districts form the Voronoi diagram for the polling places.

A Voronoi Diagram

Image

Source: A. Okabe, B. Boots and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992

A related concept is the Delaunay triangulation, which is obtained from a Voronoi diagram by drawing straight lines between each polling place and polling places in neighboring districts.

If you wish to create your own Voronoi diagram and Delaunay triangulation, go to Paul Chew's Voronoi/Delaunay Applet and follow the directions there. Use the Back button on your browser to return to this page.

Goal


This software is designed to teach students a significant mathematical concept - the Voronoi diagram - by showing its connection with modern GIS software. The program exhibits an application of classical mathematics to contemporary technology, and uses the technology to motivate the student's interest in mathematics.

Objectives


Students will learn the definitions of the Voronoi diagram and its dual, the Delaunay triangulation. They will become familiar with some applications of this geometric structure. Students will learn some of the mathematical properties of the Voronoi diagram, and will see how these properties are used in the applications.

To understand the Voronoi diagram, students need to know basic concepts in geometry such as properties of Euclidean distance, convex polygons, circles and triangles. The software will guide them to learn or review this material.

Students will get a basic understanding of the algorithm used to generate the Voronoi diagrams they see on the screen. They will gain an appreciation of the efficiency of sophisticated versus naive algorithms. Thus students will be introduced to asymptotic algorithm analysis and to computational geometry.

Methods


Students will use interactive computer graphics to create and analyze Voronoi diagrams that arise from practical applications. Wherever possible they will discover the geometric theorems that underlie the applications using the experimental method. Through hypertext, students can explore the mathematical concepts at various level of detail. Some mathematical proofs will be presented, others will be left for an accompanying text/manual. The text/manual will also present algorithmic details and references for learners who are motivated to try programming or investigate the topic in more depth.

Evaluation


There will be two sets of exercises at the end of each module. One set will require short essay-type answers, and will be self-graded. After answering each question students will see a sample answer and will be encouraged to redo the module or consult the instructor if they still have problems. The second exercise set will test for multiple-choice, numeric, or other objective answers, and can be used to show both students and instructors the extent to which students have mastered the material.

Description of Modules



Module 1

Students:

  • learn the definition of the Voronoi diagram and its many aliases.
  • use a Voronoi diagram to locate the firehouse that is nearest to a given fire in their hometown.

    Module 2

    Students learn to:

  • define half-planes and convex polygons.
  • apply the definition of a convex polygon to the naive algorithm for the construction of the Voronoi diagram.
  • determine if a set is convex.

    Module 3

    Students learn:
  • how edge, vertex, and valence are defined in graph theory.
  • why 2-valent vertices cannot occur in Voronoi diagrams.
  • why vertices with valence higher than three are very rare when sources are picked at random.
  • how to determine the circle that passes through three non-collinear points.

    Module 4

    Students learn to:

  • construct the Delaunay triangulation of a point set given the Voronoi diagram, and vice-versa.
  • understand and apply the empty circumcircle and the local max-min angle criteria.

    Module 5

    Students learn to:

  • estimate the algorithmic complexity of the naive algorithm.
  • understand the big-oh notation used in asymptotic complexity analysis through graphical representation of complexity functions.
  • compare the complexity of the naive algorithm with the O(NlogN) complexity of the best known algorithms.

    Module 6

    Students learn to:

  • apply the incremental algorithm to efficiently compute the Voronoi diagram of a set of points.
  • draw a diagram which illustrates the incremental step.
  • understand the winged-edge data structures for describing tessellations.
  • understand the quadtree data structure for spatial sorting and searching.

    Module 7

    Students learn to:
  • use Voronoi diagrams to determine the total rainfall in a drainage basin.
  • find the area of a polygon.

    Module 8

    Students learn:

  • the simplifying assumptions used when relying on a Voronoi diagram.
  • how to compute real-world distance.
  • the definition of a network Voronoi diagram.

    Module 9
    Students learn to:
  • recognize when a tessellation is a Voronoi diagram.
  • recover the source of each region in a Voronoi diagram.
  • apply the method of least squares to estimate a source when the given data is approximate.
  • apply Voronoi diagrams and the method of least squares to a problem in archaeology.

    ©1998 Peter F. Ash

    Return to Peter Ash Home Page