The ultimate strategy to search on m rays?

We consider the problem of searching on ill current rays for a target of un known location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1 + 2m(m)/(m - 1)(m-1). We show that even if an upper bound of D on the distance to the target is know n in advance, then the competitive ratio of any search strategy is at least 1 + 2m(m)/(m - 1)(m-1) - O(1/log(2) D), This is again optimal - but in a s tricter sense. In particular, this result implies the same lower bound for a robot searchi ng for a target on infinite rays and finding it at a distance of D. To show that our lower bound is, indeed, optimal we construct a search strategy th at achieves this ratio. Our strategy does not need to know an upper bound o n the distance to the target in advance; it achieves a competitive ratio of 1 + 2m(m)/(m - 1)(m-1) - O(1/log(2) D) if the target is found at distance D. Finally, we also present a linear time algorithm to compute the strategy th at allows the robot to search the farthest for a given competitive ratio C. (C) 2001 Elsevier Science B.V. All rights reserved.