Coordinating the Motion of Labeled Discs with Optimality Guarantees under Extreme Density

Rupesh Chinta, Shuai D. Han, Jingjin Yu

We push the limit in planning collision-free motions for routing uniform labeled discs in two dimensions. First, from a theoretical perspective, we show that the constant-factor ti…