In this paper, we study the following motion coordination problem: given n mobile agents and n source-destination pairs in the plane, what is the minimum time needed to transfer each agent from its source to its destination, avoiding conflicts with other agents? The environment is free of obstacles and a conflict occurs when the distance between any two agents is smaller than a velocity-dependent safety distance. In the “best” case in which the source and destination points can be chosen arbitrarily to maximize the transfer efficiency, we show that the transfer takes Theta(L sqrt(n)) time to complete, where L is the average distance between the source and destination points. We show that there exist a “worst” case distribution of the source and destination points for which the transfer of agents takes at least Omega(n) time. We also analyze the case in which source and destination points are generated randomly according to a uniform distribution, and present an algorithm providing a constructive upper bound on the time needed to transfer agents from sources to their corresponding destinations, proving that the transfer takes Theta(sqrt(n)) time, with high probability, thus recovering the best case performance. [PDF]