Schreiber Building
Computational Geometry Seminar
Wednesday, March 22nd, 2006, 16:10-18:00
Room 309
Schreiber Building
Planning corridors among obstacles has arisen as a central problem in game design. Instead of devising a one-dimensional motion path for a moving entity, it is possible to let it move in a corridor, where the exact motion path is determined by a local planner. In this paper we introduce a measure for the quality of such corridors. We analyze the structure of optimal corridors amidst point obstacles and polygonal obstacles in the plane, and propose an algorithm to compute approximations for optimal corridors.
Joint work with Jur P. van den Berg (Utrecht) and Dan Halperin.