ON CONVEX BODY CHASING

A player moving in the plane is given a sequence of instructions of th e following type: at step i a planar convex set F(i) is specified, and the player has to move to a point in F(i). The player is charged for the distance traveled. We provide a strategy for the player which is c ompetitive, i.e., for any sequence F(i) the cost to the player is with in a constant (multiplicative) factor of the ''off-line'' cost (i.e., the least possible cost when all F(i) are known in advance). We conjec ture that similar strategies can be developed for this game in any Euc lidean space and perhaps even in all metric spaces. The analogous stat ement where convex sets are replaced by more general families of sets in a metric space includes many on-line/off-line problems such as the k-server problem; we make some remarks on these more general problems.