Asymmetric Rendezvous Search on the Circle

The rendezvous search problem asks how two blind searchers in a known search region, having maximum speed one, can minimize the expected time needed to meet. Suppose that two players are placed an arc-distance x [ 0,1/2] apart on a circle of circumference 1, and faced in random directions. If x has a continuous density function h which is either decreasing and satisfies ht( 1/2) h(0)/2,or increasing, we determine an optimal rendezvous strategy. Furthermore if h is strictly monotone, this strategy (which depends in a simple manner on h) is uniquely optimal. This work extends that of J. V. Howard, who showed for the uniform density h(x) = 2 that search and wait is optimal , with expected search time 1/2. We also show that the uniform density is the only counterexample on the circle to S. Gal's conjecture (which he proved for the line) on the nonoptimality of search and wait.