2021/08/05 by Konstantinos Georgiou, Sean Leizerovich, Georgiou, Konstantinos +5
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.2108.02367
21 pages, 9 figures
arxiv created 2021/08/05 · arxiv updated 2021/08/06
The search-type problem of evacuating 2 robots in the wireless model from the (Euclidean) unit disk was first introduced and studied by Czyzowicz et al. [DISC'2014]. Since then, the problem has seen a long list of follow-up results pertaining to variations as well as to upper and lower bound improvements. All established results in the area study this 2-dimensional search-type problem in the Euclidean metric space where the search space, i.e. the unit disk, enjoys significant (metric) symmetries. We initiate and study the problem of evacuating 2 robots in the wireless model from ℓp unit disks, p ∈ [1,∞), where in particular robots' moves are measured in the underlying metric space. To the best of our knowledge, this is the first study of a search-type problem with mobile agents in more general metric spaces. The problem is particularly challenging since even the circumference of the ℓp unit disks have been the subject of technical studies. In our main result, and after identifying and utilizing the very few symmetries of ℓp unit disks, we design optimal evacuation algorithms that vary with p. Our main technical contributions are two-fold. First, in our upper bound results, we provide (nearly) closed formulae for the worst case cost of our algorithms. Second, and most importantly, our lower bounds' arguments reduce to a novel observation in convex geometry which analyzes trade-offs between arc and chord lengths of ℓp unit disks as the endpoints of the arcs (chords) change position around the perimeter of the disk, which we believe is interesting in its own right. Part of our argument pertaining to the latter property relies on a computer assisted numerical verification that can be done for non-extreme values of p.