Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq \varnothing$. Then $\bigcap_{i=1}^N X_i \neq \varnothing$.

If instead $X_1,X_2,...,X_N$ are biconvex sets in $\mathbb{R}^d$, what is "Helly's number" $h(d)$ (or an upper bound of it)?

Comment: A set $S \subseteq \mathbb{R}^{n} \times \mathbb{R}^m = \mathbb{R}^d$ is biconvex if for all $y \in \mathbb{R}^m$ the set $S_y := \{ x \in \mathbb{R}^n \mid (x,y) \in S \}$ is convex, and for all $x \in \mathbb{R}^n$ the set $S_x := \{ y \in \mathbb{R}^m \mid (x,y) \in S \}$ is convex as well.


1 Answer 1



Let $n=m=1$. We will form our sets with a braid-like construction. Each set will be a curve, and the curves will move back and forth in a fixed strip such that any $h+1$ of them intersect but all $N$ never do. We then stretch the strip out until the curves never move at an angle of more than $\pi/4$ from the length of the strip, and rotate the strip so that its length is along the line $x=y$. Thus, along each curve, $x$ and $y$ are both monotonically increasing, so $S_x$ and $S_y$ are each just a single point, hence each curve is biconvex.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .