Multi-target ray searching problems

We consider the problem of exploring m concurrent rays using a searcher. The rays are disjoint with the exception of a single common point, and in each ray at most one potential target may be located. The objective is to design search strategies for locating t targets (with t ⩽ m ) while minimizing the search distance traversed. This setting generalizes the extensively studied ray search (or star search) problem, in which the searcher seeks a single target. We apply two different measures for evaluating the efficiency of the search strategy. The first measure is the standard metric in the context of ray-search problems, and compares the total search cost to the cost of an optimal algorithm that has full information on the targets. We present a simple strategy that achieves optimal competitive ratio under this metric. Our main result pertains to the second measure, which is based on a weakening of the optimal cost as proposed by Kirkpatrick [ESA 2009] and McGregor et al. [ESA 2009]. For this model, we present an asymptotically optimal strategy that is within a multiplicative factor of Θ ( log ( m − t ) ) from the optimal search cost. Our results demonstrate that, for both problems, the problem of locating t targets in m rays is essentially as difficult as the problem of locating a single target in m − ( t − 1 ) rays.

Authors

• Spyros Angelopoulos
• Alejandro López-Ortiz
• Konstantinos Panagiotou

Keywords

• Search and exploration algorithms
• Ray searching
• Competitive analysis of online algorithms
• Alternative performance measures