2019/05/25 by Yann Disser, Disser, Yann, Sören Schmitt +1 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1905.10592
19 pages, 5 figures. This is the full version of the paper with the same title accepted in the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO'19)
arxiv created 2019/05/25 · arxiv updated 2019/05/28
We present an improved algorithm for the problem of evacuating two robots from the unit disk via an unknown exit on the boundary. Robots start at the center of the disk, move at unit speed, and can only communicate locally. Our algorithm improves previous results by Brandt et al. [CIAC'17] by introducing a second detour through the interior of the disk. This allows for an improved evacuation time of 5.6234. The best known lower bound of 5.255 was shown by Czyzowicz et al. [CIAC'15].