Lower bounds in on-line geometric searching

We present a new technique to prove lower bounds for geometric on-line sear ching problems. We assume that a target of unknown location is hidden somew here in a known environment and a searcher is trying to find it. We are int erested in lower bounds on the competitive ratio of the search strategy, th at is, the ratio of the distance traveled by the searcher to the distance o f the target. The technique we present is applicable to a number of problems, such as bia sed searching on m rays and on-line construction of on-line algorithms. For each problem we prove tight lower bounds. (C) 2001 Elsevier Science B.V. A ll rights reserved.