Alternating search at two locations

In this paper we introduce a new class of search problem which we call ‘alternating search’. Two searchers starting at given points in different search regions, who can move alternately with speed one, or (as a limiting case) simultaneously with combined speed one, seek to find (reach) an object in least expected time. The hidden object is stationary and its location is given by a known distribution over the union of the two search regions. An important special case is the ‘Double Linear Search Problems’ in which both search regions are infinite lines, and which has been shown to be equivalent to the ‘Asymmetric Rendezvous Search Problem on the Line’ (ARSPL). The general results proved here are applied in a concurrent paper of Alpern and Beck to prove that the strategy conjectured by Baston and Gal to be optimal for the convex ARSPL is indeed optimal. Our general results are concerned with determining the method of interleaving two given distributions so as to minimize the first moment of the resulting distribution.