Competitive online searching for a ray in the plane

Abstract. We consider the problem of a searcher that looks, for exam-ple, for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the flashlight, and in order to pick it up, the searcher has to move to the origin of the light beam. First, we give a search strategy for a special case of the ray search—the window shopper problem—, where the ray we are looking for is perpen-dicular to a known ray. Our strategy achieves a competitive factor of ≈1.059, which is optimal. Then, we consider the search for a ray with an arbitrary position in the plane. We present an online strategy that achieves a factor of ≈22.513, and give a lower bound of ≈17.079