The University of Arizona

Events & News


DateTuesday, March 25, 2014
Time11:00 am
Concludes12:00 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refreshments at 10:45am in the 9th Floor Atrium.

Faculty Host: Stephen Kobourov
SpeakerMatt Dickerson
AffiliationMiddlebury College

The Post Office Problem, Practically (For When You Drive On Roads & Visit Grocery Stores Too)

Donald Knuth’s famous "post office problem" is often used as a motivating example for Voronoi diagrams. But a purely geometric version of Voronoi diagrams does not actually provide a practical solution to the problem—unless everybody travels in helicopters. And what if somebody wants to run an errand to the grocery store as well as the post office? In this talk we will explore how to plan an efficient round trip visit to the post office and the grocery store (or the bank and elementary school) for those who actually travel on roads. In particular, we will explore the properties and algorithmic construction of two-site Voronoi diagrams on geographic networks.


Matthew Dickerson is a professor of Computer Science at Middlebury College in Vermont. He has a Ph.D. in Computer Science from Cornell University and does research in computational geometry and in agent-based modeling of killer whales. When he is not doing research in computer science he is a novelist (THE ROOD AND THE TORC) and national known Tolkien scholar (A HOBBIT JOURNEY).