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 quantitative 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 according to our measure.
This work has been supported in part by the IST Programme of the EU as Shared-cost RTD (FET Open) Projects under Contract
No IST-2001-39250 (MOVIE — Motion Planning in Virtual Environments) and IST-006413 (ACS - Algorithms for Complex Shapes) ,
and by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University.