{"data":{"id":"10.48550/arxiv.1008.4420","type":"dois","attributes":{"doi":"10.48550/arxiv.1008.4420","prefix":"10.48550","suffix":"arxiv.1008.4420","identifiers":[{"identifier":"1008.4420","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1008.4420"}],"creators":[{"name":"Fekete, Sandor P.","nameType":"Personal","givenName":"Sandor P.","familyName":"Fekete","affiliation":[],"nameIdentifiers":[]},{"name":"Gray, Chris","nameType":"Personal","givenName":"Chris","familyName":"Gray","affiliation":[],"nameIdentifiers":[]},{"name":"Kroeller, Alexander","nameType":"Personal","givenName":"Alexander","familyName":"Kroeller","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Evacuation of rectilinear polygons"}],"publisher":"arXiv","container":{},"publicationYear":2010,"subjects":[{"lang":"en","subject":"Data Structures and Algorithms (cs.DS)","subjectScheme":"arXiv"},{"lang":"en","subject":"Computational Complexity (cs.CC)","subjectScheme":"arXiv"},{"lang":"en","subject":"Computational Geometry (cs.CG)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"lang":"en","subject":"F.2.2","subjectScheme":"ACM"}],"contributors":[],"dates":[{"date":"2010-08-26T03:07:28Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2015-05-19T14:14:37Z","dateType":"Updated","dateInformation":"v1"},{"date":"2010-08","dateType":"Available","dateInformation":"v1"},{"date":"2010","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1007/978-3-642-17458-2_3","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"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).","descriptionType":"Abstract"},{"description":"15 pages, 7 figures; to appear in COCOA 2010","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xMDA4LjQ0MjA8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xMDA4LjQ0MjA8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+RmVrZXRlLCBTYW5kb3IgUC48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlNhbmRvciBQLjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5GZWtldGU8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+R3JheSwgQ2hyaXM8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkNocmlzPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkdyYXk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+S3JvZWxsZXIsIEFsZXhhbmRlcjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+QWxleGFuZGVyPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPktyb2VsbGVyPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5FdmFjdWF0aW9uIG9mIHJlY3RpbGluZWFyIHBvbHlnb25zPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDEwPC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+RGF0YSBTdHJ1Y3R1cmVzIGFuZCBBbGdvcml0aG1zIChjcy5EUyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5Db21wdXRhdGlvbmFsIENvbXBsZXhpdHkgKGNzLkNDKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkNvbXB1dGF0aW9uYWwgR2VvbWV0cnkgKGNzLkNHKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iQUNNIj5GLjIuMjwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTAtMDgtMjZUMDM6MDc6MjhaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTUtMDUtMTlUMTQ6MTQ6MzdaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IkF2YWlsYWJsZSIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMC0wODwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iVGV4dCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDxyZWxhdGVkSWRlbnRpZmllcnM+CiAgICA8cmVsYXRlZElkZW50aWZpZXIgcmVsYXRlZElkZW50aWZpZXJUeXBlPSJET0kiIHJlbGF0aW9uVHlwZT0iSXNWZXJzaW9uT2YiPjEwLjEwMDcvOTc4LTMtNjQyLTE3NDU4LTJfMzwvcmVsYXRlZElkZW50aWZpZXI+CiAgPC9yZWxhdGVkSWRlbnRpZmllcnM+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGludmVzdGlnYXRlIHRoZSBwcm9ibGVtIG9mIGNyZWF0aW5nIGZhc3QgZXZhY3VhdGlvbiBwbGFucyBmb3IgYnVpbGRpbmdzIHRoYXQgYXJlIG1vZGVsZWQgYXMgZ3JpZCBwb2x5Z29ucywgcG9zc2libHkgY29udGFpbmluZyBleHBvbmVudGlhbGx5IG1hbnkgY2VsbHMuIFdlIHN0dWR5IHRoaXMgcHJvYmxlbSBpbiB0d28gY29udGV4dHM6IHRoZSBgYGNvbmZsdWVudCcnIGNvbnRleHQgaW4gd2hpY2ggdGhlIHJvdXRlcyB0byBleGl0cyByZW1haW4gZml4ZWQgb3ZlciB0aW1lLCBhbmQgdGhlIGBgbm9uLWNvbmZsdWVudCcnIGNvbnRleHQgaW4gd2hpY2ggcm91dGVzIG1heSBjaGFuZ2UuIENvbmZsdWVudCBldmFjdWF0aW9uIHBsYW5zIGFyZSBzaW1wbGVyIHRvIGNhcnJ5IG91dCwgYXMgdGhleSBhbGxvY2F0ZSBjb250aWd1b3VzIHJlZ2lvbnMgdG8gZXhpdHM7IG5vbi1jb25mbHVlbnQgYWxsb2NhdGlvbiBjYW4gcG9zc2libHkgY3JlYXRlIGZhc3RlciBldmFjdWF0aW9uIHBsYW5zLiBXZSBnaXZlIHJlc3VsdHMgb24gdGhlIGhhcmRuZXNzIG9mIGNyZWF0aW5nIHRoZSBldmFjdWF0aW9uIHBsYW5zIGFuZCBzdHJvbmdseSBwb2x5bm9taWFsIGFsZ29yaXRobXMgZm9yIGZpbmRpbmcgY29uZmx1ZW50IGV2YWN1YXRpb24gcGxhbnMgd2hlbiB0aGUgYnVpbGRpbmcgaGFzIHR3byBleGl0cy4gV2UgYWxzbyBnaXZlIGEgcHNldWRvLXBvbHlub21pYWwgdGltZSBhbGdvcml0aG0gZm9yIG5vbi1jb25mbHVlbnQgZXZhY3VhdGlvbiBwbGFucy4gRmluYWxseSwgd2Ugc2hvdyB0aGF0IHRoZSB3b3JzdC1jYXNlIGJvdW5kIGJldHdlZW4gY29uZmx1ZW50IGFuZCBub24tY29uZmx1ZW50IHBsYW5zIGlzIDItMi8oaysxKS48L2Rlc2NyaXB0aW9uPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iT3RoZXIiPjE1IHBhZ2VzLCA3IGZpZ3VyZXM7IHRvIGFwcGVhciBpbiBDT0NPQSAyMDEwPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/1008.4420","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-14T01:49:41.000Z","registered":"2022-03-14T01:49:42.000Z","published":"2010","updated":"2022-03-14T01:49:42.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1008.4420","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}