Search

We study online competitive algorithms for the line chasing problem in Euclidean spaces Rd, where the input consists of an initial point P0 and a sequence of lines X1,X2,...,Xm, revealed one at a time. At each step t, when the line Xt is revealed, the algorithm must determine a point Pt ∈ Xt. An online algorithm is called c-competitive if for any input sequence the path P0, P1, ..., Pm it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets Xt are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of √2 ≈ 1.412 for convex body chasing in 2 dimensions.