On the two-dimensional cow search problem
We investigate the problem introduced by Baeza-Yates et al. [R.A. Baeza-Yates, J.C. Culberson, G.J.E. Rawlins, Searching with uncertainty, Research report, University of Waterloo, 1987]: given a plane and a horizontal or a vertical line in unknown location give a strategy to find this line. We use a competitive analysis to measure the performance of this strategy. This problem is one of the first generalisations of the cow search problem. (C) 2009 Elsevier B.V. All rights reserved.
search problems uncertainty on-line algorithms