Consider the following classical search problem: given a target point p ∈ ℝ, starting at the origin, find p with minimum cost, where cost is defined as the distance travelled. When no lower bound on |p| is given, no competitive search strategy exists. Demaine, Fekete and Gal [1] considered the situation where no lower bound on |p| is given but a fixed turn cost t > 0 is charged every time the searcher changes direction. When the total cost is expressed as γ |p| + φ, where γ and φ are positive constants, they showed that if γ is set to 9, then the optimal search strategy has a cost of 9 |p| + 2 t. Although their strategy is optimal for γ = 9, we prove that the minimum cost in their framework is 5 |p| + t + 2 √(2 |p| (2 |p| + t)) < 9|p| + 2 t. Note that the minimum cost requires knowledge of |p|, however, given |p|, the optimal strategy has a smaller cost of 3 |p| + t. Therefore, this problem cannot be solved optimally when no lower bound on |p| is given.

To resolve this issue, we introduce a general framework where the cost of moving distance x away from the origin is α₁ x+β₁ and the cost of moving distance y towards the origin is α₂ y+β₂ for constants α₁, α₂, β₁, β₂. Given a lower bound λ on |p|, we provide a provably optimal competitive search strategy when α₁, α₂ ≥ 0, α₁ + α₂ > 0, β₁, β₂ ≥ 0. We show how our framework encompasses many of the results in the literature, and also point out its relation to other frameworks that have been proposed.

Finally, we address the problem of searching for a target lying on one of m rays extending from the origin where the cost is measured as the total distance travelled plus t ≥ 0 times the number of turns. We provide a search strategy and compute its cost. We prove our strategy is optimal for small values of t and conjecture it is always optimal.

[1] Demaine, Fekete and Gal. Online searching with turn cost, Theor. Comput. Sci., 361(2-3):342-355, 2006