{"id":"arxiv/2610.32670","url":"https://arxiv.org/abs/2610.32670","tags":["cs.DS","cs.CG","math.MG"],"score":0,"title":"A Linear Lower Bound for Convex Body Chasing in Every $\\ell_p$ Norm","domain":"cs.DS","source":"arxiv","authors":["Nicolas Christianson"],"reviews":0,"subject":"cs.DS","summary":"We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\\mathbb{R}^d$ with $\\ell_p$ movement costs for any $p \\in [1, \\infty)$. Previously, the best known lower bound for general $p$ was $Ω(\\max\\{\\sqrt{d}, d^{1-1/p}\\})$, established by Bubeck et al. (2019); a linear lower bound was known only for $p = \\infty$, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed $p \\in [1, \\infty)$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-23","reactions":{}}