2
$\begingroup$

Consider the following:

1) How many connected regions can $n$ hyperplanes form in $\mathbb R^d$?

2) What if the set of hyperplanes are homogeneous?

3) Given a set of $n$ pairs of hyperplanes, such that each pair is parallel, what is the maximum number of regions that can be formed?

I saw here,here and here that the answer to (1) is $$f(d,n)=\sum_{i=0}^d {n \choose i}$$

However I find it non-trivial to generalize the proof of $\mathbb R^2$ that was provided to $\mathbb R^d$ (without using "lower"/"upper" descriptions). Is there any "nice" way to show it recursively?

Q3 is what I'm really after.

Any ideas?

$\endgroup$
2
$\begingroup$

Use Radon's theorem to show that homogeneous hyperplanes $w$ can shatter (i.e., assign all possible sign sequences via $x\mapsto\text{sign}(<w,x>)$ at most $d$ points. This is an upper bound on the VC-dimension on hyperplanes (which turns out to be tight). Then use the Sauer-Shelah lemma to bound the number of behaviors that the hyperplanes can attain on $n$ points

That accounts for the formula $\sum_{i=1}^d {n\choose i}$.

As for pairs of hyperplanes, I'll use a very crude bound for VC-dimension of intersections of pairs of sets from a VC-class of dimension $d$, see Theorem 3.6 in Kearns-Vazirani or this paper by Baum and Haussler, to get that the VC-dimension of the collection of pairs of hyperplanes in $d$ dimensions is at most $20d$. You can then apply Sauer-Shelah to this new value of VC-dimension.

$\endgroup$
2
$\begingroup$

Suppose we have $n$ sets of $r$ parallel hyperplanes in $\mathbb{R}^d$ in generic position. There are $r^k\binom nk$ ways to choose $k$ of them that intersect in a flat $x$. The interval from $\hat{0}$ to $x$ in the intersection poset is a boolean algebra, so the Mobius function is given by $\mu(\hat{0},x)=\pm 1$. Thus by Zaslavsky's theorem, the number of regions is $\sum_{k=0}^d r^k\binom nk$.

$\endgroup$
  • $\begingroup$ For a much less elegant proof of this formula (by people who don't know any theorems) see Lemma 3 in this paper: arxiv.org/abs/1508.03181 $\endgroup$ – Thomas Kalinowski Jan 3 '17 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.