2010/01/01 by Sándor P. Fekete, Sandor P. Fekete, Chris Gray +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Computational Geometry and Mesh Generation #Computer science #Context (archaeology) #Geometry #Grid #Mathematical optimization #Mathematics #Optimization and Search Problems #Polynomial #Theoretical computer science #Time complexity #cs.CC #cs.CG #cs.DS
paper · pdf · doi:10.1007/978-3-642-17458-2_3
15 pages, 7 figures; to appear in COCOA 2010
openalex publication_date 2010/01/01 · arxiv created 2010/08/26 · arxiv updated 2015/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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).