Evacuation of rectilinear polygons

Details Evacuation of rectilinear polygons Evacuation of rectilinear polygons

2010-08-26

arxiv.org/abs/1008.4420v1

Computer Science

Data Structures and Algorithms

15 pages, 7 figures; to appear in COCOA 2010

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Evacuation of rectilinear polygons does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Evacuation of rectilinear polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evacuation of rectilinear polygons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-703605