A Fire Fighter's Problem.

Summary, in English

Suppose that a circular fire spreads in the plane at unit speed. A fire fighter can build a barrier at speed v > 1. How large must v be to ensure that the fire can be contained, and how should the fire fighter proceed? We provide two results. First, we analyze the natural strategy where the fighter keeps building a barrier along the frontier of the expanding fire. We prove that this approach contains the fire if v > v_c = 2.6144... holds. Second, we show that any "spiralling" strategy must have speed v > 1.618, the golden ratio, in order to succeed.

• Författare: Rolf Klein; Elmar Langetepe; Christos Levcopoulos
• Redaktör: Lars Arge; Janos Pach
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2015
• Språk: Engelska
• Sidor: 768-780
• Publikation/Tidskrift/Serie: Leibniz International Proceedings in Informatics (LIPIcs)
• Volym: 34
• Länkar: http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.768
• Dokumenttyp: Konferensbidrag
• Förlag: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Ämne: Computer Science
• Nyckelord: Motion Planning; Dynamic Environments; Spiralling strategies; Lower and upper bounds
• Conference name: 31st International Symposium on Computational Geometry (SoCG 2015)
• Conference date: 2015-06-22
• Conference place: Netherlands
• Status: Published
• Forskningsgrupp: Algorithms
• ISBN/ISSN/Övrigt: ISSN: 1868-8969