Lower bounds in on-line geometric searching

AbstractWe present a new technique to prove lower bounds for geometric on-line searching problems. We assume that a target of unknown location is hidden somewhere in a known environment and a searcher is trying to find it. We are interested in lower bounds on the competitive ratio of the search strategy, that is, the ratio of the distance traveled by the searcher to the distance of the target.The technique we present is applicable to a number of problems, such as biased searching on m rays and on-line construction of on-line algorithms. For each problem we prove tight lower bounds