Geometric Shortest Path and Optimal Network Problems: Some Recent Results and Continuing Challenges

Event time: 
Wednesday, April 13, 2005 - 12:30pm to Tuesday, April 12, 2005 - 8:00pm
Location: 
215 LOM
Speaker: 
Joseph Mitchell
Speaker affiliation: 
SUNY at Stony Brook
Event description: 

What is the best strategy for mowing one’s lawn? How should a
traveling salesperson visit a set of cities or regions while traveling
the shortest distance? How should a robot move efficiently within a
building in order to be able to see every nook and cranny? What is
the best strategy to “unfreeze” your teammates in a game of freeze-tag?
How should an industrial milling tool be guided in order to shape a
particular part? Where should security cameras be placed in order to
provide robust surveillance of an airport terminal?

These are all examples of shortest path and network optimization
problems that arise in geometric settings and are studied within the
field of computational geometry. Almost all versions of these
problems are provably hard, from the point of view of complexity of
algorithms, so our efforts often focus on solving special cases
exactly, devising approximation algorithms that have some provable
performance guarantee, and designing heuristic methods that have good
experimental behavior in practice. We survey some of our recent work
on geometric optimization of paths, tours, and networks, with
applications in robotics, sensor networks, vehicle routing, and
manufacturing. We will highlight several outstanding open problems
under current investigation.

Special note: 
CANCELLED (will reschedule)