Department of
Applied
Mathematics

Nested Convex Bodies are Chaseable (J. Matou¹ek prize talk)

Martin Böhm

Abstract

(joint work with Nikhil Bansal, Marek Eliá¹, Grigorios Koumoutsos and Seeun William Umboh)

In the Convex Body Chasing problem, we are given an initial point v in R^d and an online sequence of n convex bodies F_1,...,F_n. When we receive F_i, we are required to move inside F_i. Our goal is to minimize the total distance travelled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an Omega(sqrt(d)) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open.

In this work, we give a simple f(d)-competitive algorithm for chasing *nested* convex bodies in R^d, i.e. when F_2 lies inside F_1, F_3 lies inside F_2 and so on. Among other consequences, this indicates that the problem is considerably more difficult when the optimal path visits several points, as opposed to just moving to a single globally feasible position.