Parallel Searching on a Lattice. A. López-Ortiz and G. Sweet. Proceedings of the 13th Canadian Conference on Computational Geometry, (CCCG), pp.125-128, 2001. PostScript file.

 

Abstract. We consider the problem of k robots searching on an integer lattice on the plane. We give a strategy for finding a target at an unknown distance away using k=2^j searchers, where j >= 2, at a competitive ratio of n/2^{j-1}+1. We give a lower bound for general k$ of 2n/k. We also give matching upper and lower bounds for the special case k=2.