Middlebury College
Department of Computer Science Seminar
A Quick Trip to School and the Post Office:
Road Networks and Voronoi Diagrams
Matthew Dickerson
Middlebury College
Dept. of Computer Science
Suppose you have computerized map (GIS database) of all the roads and parkways in Pennsylvania as well as lists of interesting places like police stations, post offices, pizza parlors, and primary schools. For any location on that map, you'd like to be able to answer questions like: What is the nearest post office? What is the closest pair of pizza parlors or police stations? If I want to post a letter and pick up a pizza, traveling the minimum distance, how can I do it? We will take an informal first glance at some new work that Professor Dickerson is doing with a colleague at U.C.Irvine that provides efficient computational approaches to these questions, and others like them. If you know what a road, a map, a post office, and an algorithm are, you will be able to understand most of this talk. In the process, you will learn what a Voronoi diagram is, and hear a reference to Dijkstra's single source shortest path algorithm.
Professor Matthew Dickerson is in the Department of Computer Science and the Program of Environmental Studies. He has published several dozen papers in computational geometry and related fields like graph algorithms and data structures. He is especially interested in solving the following variant of the above question: "What is the nearest place to find good fishing?"
Wednesday, February 27, 2008
12:30 p.m. to 1:20 p.m.
McCardell Bicentennial Hall 538
Lunch will be provided at 12:20 p.m.
All are welcome to attend!
This event is sponsored by the Computer Science Department.