Optimal Convex Hull Formation on a Grid by Asynchronous Robots With Lights

Abstract

We consider the distributed setting of <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using a constant number of colored lights (the <i>robots with lights</i> model). We assume obstructed visibility where collinear robots do not see each other. In addition, we consider a grid-based terrain embedded in the 2-dimensional euclidean plane. The <small>Convex Hull Formation</small> problem is to relocate the <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this article, we provide a framework for solving <small>Convex Hull Formation</small> . We then provide four asynchronous algorithms under this framework. Key measures of the algorithms’ performance include the time taken and the space occupied. The presented algorithms are randomized and their time bounds hold with high probability. The first <inline-formula><tex-math notation="LaTeX">$O(\max \lbrace n^{2},D\rbrace)$</tex-math></inline-formula> -time, <inline-formula><tex-math notation="LaTeX">$O({n^{2}})$</tex-math></inline-formula> -perimeter, and <inline-formula><tex-math notation="LaTeX">$O({n^{3}})$</tex-math></inline-formula> -area algorithm serves to introduce key ideas, where <inline-formula><tex-math notation="LaTeX">$D$</tex-math></inline-formula> is the diameter of the initial configuration. The subsequent algorithms, differing in computational requirements, run in <inline-formula><tex-math notation="LaTeX">$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)$</tex-math></inline-formula> time with a perimeter of <inline-formula><tex-math notation="LaTeX">$O(n^{\frac{3}{2}})$</tex-math></inline-formula> and area of <inline-formula><tex-math notation="LaTeX">$O(n^{3})$</tex-math></inline-formula> . We also prove lower bounds of <inline-formula><tex-math notation="LaTeX">$\Omega (n^{\frac{3}{2}})$</tex-math></inline-formula> for time and perimeter and <inline-formula><tex-math notation="LaTeX">$\Omega (n^{3})$</tex-math></inline-formula> for area, for any <small>Convex Hull Formation</small> algorithm; i.e., our <inline-formula><tex-math notation="LaTeX">$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)-$</tex-math></inline-formula> time algorithm is optimal in time, perimeter, and area.