arXiv · Oct 23, 2026
A Linear Lower Bound for Convex Body Chasing in Every ℓ_p Norm
By Nicolas Christianson
We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in R^d with ℓ_p movement costs for any p ∈ [1, ∞). Previously, the best known lower bound for general p was Ω(max{√d, d^(1-1/p)}), established by Bubeck et al. (2019); a linear lower bound was known only for p = ∞, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed p ∈ [1, ∞) and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio O(d) - is asymptotically optimal for every ℓ_p norm. Our lower bound is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of Ω(r²) for requests of size O(r) in that setting. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a (2r+1)-dimensional vector space while approximately preserving movement costs up to a factor of O(r), which establishes the lower bound.