Helly numbers of Algebraic Subsets of ${\mathbb{R}}^d$

Abstract

We study $S$-convex sets, which are the geometric objects obtained as the intersection of the usual convex sets in ${\mathbb{R}}^d$ with a proper subset $S\subset {\mathbb{R}}^d$. We contribute new results about their $S$-Helly numbers. We extend prior work for $S={\mathbb{R}}^d$, ${\mathbb{Z}}^d$, and ${\mathbb{Z}}^{d-k}\times {\mathbb{R}}^k$; we give sharp bounds on the $S$-Helly numbers in several new cases. We considered the situation for low-dimensional $S$ and for sets $S$ that have some algebraic structure, in particular when $S$ is an arbitrary subgroup of ${\mathbb{R}}^d$ or when $S$ is the difference between a lattice and some of its sublattices. By abstracting the ingredients of Lovász method we obtain colorful versions of many monochromatic Helly-type results, including several colorful versions of our own results.

13 pages, 3 figures. This paper is a revised version of what was originally the first half of arXiv:1504.00076v1

References in corpus (3)

• Quantitative Tverberg, Helly, & Carathéodory theorems
• A Quantitative Doignon-Bell-Scarf Theorem
• Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization

Cited by in corpus (2)

• Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
• Centerpoints: A link between optimization and convex geometry