Lipschitz Selectors May Not Yield Competitive Algorithms for Convex Body Chasing

C. J. Argue, Anupam Gupta, Marco Molinaro

Research output: Contribution to journalArticlepeer-review


The current best algorithms for the convex body chasing (CBC) problem in online algorithms use the notion of the Steiner point of a convex set. In particular, the algorithm that always moves to the Steiner point of the request set is O(d) competitive for nested CBC, and this is optimal among memoryless algorithms [Bubeck et al.: Chasing nested convex bodies nearly optimally. In: 31st Annual ACM–SIAM Symposium on Discrete Algorithms (Salt Lake City 2020), pp. 1496–1508. SIAM, Philadelphia (2020)]. A memoryless algorithm coincides with the notion of a selector in functional analysis. The Steiner point is noted for being Lipschitz with respect to the Hausdorff metric, and for achieving the minimal Lipschitz constant possible. It is natural to ask whether every selector with this Lipschitz property yields a competitive algorithm for nested CBC. We answer this question in the negative by exhibiting a selector that yields a non-competitive algorithm for nested CBC but is Lipschitz with respect to Hausdorff distance. Furthermore, we show that being Lipschitz with respect to an Lp -type analog of the Hausdorff distance is sufficient to guarantee competitiveness if and only if p= 1 .

Original languageEnglish (US)
Pages (from-to)773-789
Number of pages17
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - Oct 2023


  • Convex body chasing
  • Hausdorff distance
  • Lipschitz
  • Online algorithms
  • Selector

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Lipschitz Selectors May Not Yield Competitive Algorithms for Convex Body Chasing'. Together they form a unique fingerprint.

Cite this