  In the chasing convex bodies problem, an online player receives a request
sequence of $N$ convex sets $K_1,\dots, K_N$ contained in a normed space
$\mathbb R^d$. The player starts at $x_0\in \mathbb R^d$, and after observing
each $K_n$ picks a new point $x_n\in K_n$. At each step the player pays a
movement cost of $||x_n-x_{n-1}||$. The player aims to maintain a constant
competitive ratio against the minimum cost possible in hindsight, i.e. knowing
all requests in advance. The existence of a finite competitive ratio for convex
body chasing was first conjectured in 1991 by Friedman and Linial. This
conjecture was recently resolved with an exponential $2^{O(d)}$ upper bound on
the competitive ratio.
  We give an improved algorithm achieving competitive ratio $d$ in any normed
space, which is exactly tight for $\ell^{\infty}$. In Euclidean space, our
algorithm also achieves competitive ratio $O(\sqrt{d\log N})$, nearly matching
a $\sqrt{d}$ lower bound when $N$ is subexponential in $d$. The approach
extends our prior work for nested convex bodies, which is based on the
classical Steiner point of a convex body. We define the functional Steiner
point of a convex function and apply it to the associated work function.

Data Structures and Algorithms;Metric Geometry