Parallel Searching on a Lattice

[.ps] [.pdf]


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=2j searchers, where j ≥ 2, at a competitive ratio of n/2j-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.

Bibtex Entry