  We investigate the problem of creating fast evacuation plans for buildings
that are modeled as grid polygons, possibly containing exponentially many
cells. We study this problem in two contexts: the ``confluent'' context in
which the routes to exits remain fixed over time, and the ``non-confluent''
context in which routes may change. Confluent evacuation plans are simpler to
carry out, as they allocate contiguous regions to exits; non-confluent
allocation can possibly create faster evacuation plans. We give results on the
hardness of creating the evacuation plans and strongly polynomial algorithms
for finding confluent evacuation plans when the building has two exits. We also
give a pseudo-polynomial time algorithm for non-confluent evacuation plans.
Finally, we show that the worst-case bound between confluent and non-confluent
plans is 2-2/(k+1).

Data Structures and Algorithms;Computational Complexity;Computational Geometry