Parallel searching on a lattice.

Abstract

We consider the problem of k robots searching on an integer lattice on the plane. We give a strategy for nding 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. 1