Better Bounds for Online Line Chasing

We study online competitive algorithms for the line chasing problem in Euclidean spaces realsd, 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 significantly improve this bound, by providing a~3-competitive algorithm for any dimension d. We also improve the lower bound on the competitive ratio, from 1.412 to 1.5358.