Consider k robots initially located at the centroid of an equilateral triangle T of sides of length one. The goal of the robots is to evacuate T through an exit at an unknown location on the boundary of T. Each robot can move anywhere in T independently of other robots with maximum speed one. The objective is to minimize the evacuation time, which is defined as the time required for all k robots to reach the exit. We consider the face-to-face communication model for the robots: a robot can communicate with another robot only when they meet in T. In this paper, we give upper and lower bounds for the face-to-face evacuation time by k robots. We show that for any k, any algorithm for evacuating k >= 1 robots from T requires at least sqrt(3) time. This bound is asymptotically optimal, as we show that a straightforward strategy of evacuation by k robots gives an upper bound of sqrt(3) + 3/k. For k = 3, 4, 5, 6, we show significant improvements on the obvious upper bound by giving algorithms with evacuation times of 2.0887, 1.9816, 1.876, and 1.827, respectively. For k = 2 robots, we give a lower bound of 1 + 2/sqrt(3) ~= 2.154, and an algorithm with upper bound of 2.3367 on the evacuation time.


    Access

    Download


    Export, share and cite



    Title :

    Evacuating an Equilateral Triangle in the Face-to-Face Model


    Contributors:

    Publication date :

    2018-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Equilateral triangle helicopter

    JIANG FUYU | European Patent Office | 2020

    Free access

    Analysis of equilateral triangle semiconductor microlasers with rough sidewalls

    Yong-Zhen Huang, / Wei-Hua Guo, / Li-Juan Yu, et al. | IEEE | 2001


    Analysis of Equilateral Triangle Semiconductor Microlasers with Rough Sidewalls

    Huang, Y.-Z. / Guo, W.-H. / Yu, L.-J. et al. | British Library Conference Proceedings | 2001


    Evacuating Offshore Structures

    Simoees, A. J. | British Library Conference Proceedings | 1997


    Evacuating hospital theatres

    Orr, R. | British Library Online Contents | 1995