10
$\begingroup$

Given $n$ points in $\mathbb{R}^d$ in general position, where $n\geq d+1$. For every $d$ points, form the hyperplane defined by these $d$ points. These hyperplanes cut $\mathbb{R}^d$ into several regions. My questions are:
(1) is there a formula in terms of $d$ and $n$ that describes the number of regions?
(2) the same question for the number of bounded regions?

I tried many key words on google but found nothing helpful. Any reference or ideas will be appreciated. Thanks

$\endgroup$
6
  • $\begingroup$ General position as defined in en.wikipedia.org/wiki/General_position $\endgroup$
    – Min Wu
    Feb 19, 2020 at 4:27
  • 3
    $\begingroup$ Can you maybe elaborate? Both for the general position arrangement where all 4 points lie on the boundary of their convex hull, as well as for the arrangement where one point lies in the interior, I count 6 bounded regions. $\endgroup$ Feb 19, 2020 at 7:29
  • 1
    $\begingroup$ The maximum number of cells in an arrangement of $k$ hyperplanes in dimension $d$ is $O(k^d)$. Your $k$ is $\binom{n}{d}$. $\endgroup$ Feb 19, 2020 at 11:56
  • $\begingroup$ @JosephO'Rourke Thanks for the info. Can you direct me to a reference where I can find the results? $\endgroup$
    – Min Wu
    Feb 19, 2020 at 17:59
  • 1
    $\begingroup$ @GHfromMO I think you are right, the number of bounded regions may vary from case to case. I am wondering whether the total number of regions would also vary or just be the same? $\endgroup$
    – Min Wu
    Feb 19, 2020 at 18:01

3 Answers 3

9
$\begingroup$

This is more of a long comment than an answer. It should be possible to compute the number of regions and number of bounded regions using Whitney's theorem for the characteristic polynomial $\chi(t)$ (Theorem 2.4 of these notes), and Zaslavsky's theorem that the number of regions is $(-1)^d \chi(-1)$, and the number of bounded regions is (in this situation) $(-1)^d\chi(1)$ (Theorem 2.5 of the previous link). We need more than the usual definition of "general position." We want the position to be generic enough for the argument below (generalized to $d$ dimensions) to hold.

Here is the computation for $d=2$. First, the empty intersection (the ambient space $\mathbb{R}^2$) contributes $t^2$ to $\chi(t)$. The ${n\choose 2}$ lines will contribute $-{n\choose 2}t$. Now we must consider all subsets of the lines that intersect in a point $p$. Let $p$ be one of the original $n$ points. Then ${n-1\choose 2}$ pairs of lines intersect in $p$, ${n-1\choose 3}$ triple of lines intersect in $p$, etc., giving a contribution to $\chi(t)$ of $$ {n-1\choose 2}-{n-1\choose 3}+{n-1\choose 4} -\cdots = n-2. $$ We have to multiply this by $n$ since there are $n$ choices for $p$. There are now $3{n\choose 4}$ choices of two lines that don't intersect in one of the original $n$ points, but they still intersect by genericity. Thus we get an additional contribution of $3{n\choose 4}$. It follows that $$ \chi(t) = t^2-{n\choose 2}t+n(n-2)+3{n\choose 4}. $$ The number of regions is $$ \chi(-1) = \frac 18(n-1)(n^3-5n^2+18n-8). $$ The number of bounded regions is $$ \chi(1) = \frac 18(n-1)(n-2)(n^2-3n+4). $$ Can someone extend this argument to $d$ dimensions?

Addendum. I worked out $d=3$. Here are the details. Let $X$ be an $n$-element "generic" subset of $\mathbb{R}^3$. Thus $X$ determines a set $\mathcal{A}$ of ${n\choose 3}$ hyperplanes. We need to find all subsets of $\mathcal{A}$ with nonempty intersection. A $j$-element subset that intersects in an $e$-dimensional affine space contributes $(-1)^jt^e$ to the characteristic polynomial $\chi(t)$.

Case 1: $e=3$. We take the intersection over the empty set to get $\mathbb{R}^3$. This gives a term $t^3$.

Case 2: $e=2$. Each hyperplane contributes $-t^2$, giving a term $-{n\choose 3}t^2$.

Case 3: $e=1$. (a) Any two hyperplanes intersect in a line (by genericity), giving ${{n\choose 3}\choose 2}t$.

(b) Any $j\geq 3$ hyperplanes containing the same two points $p,q\in X$ meet in a line. There are ${n\choose 2}$ choices for $p,q$ and ${n-2\choose j}$ for the remaining element of $X$ in the hyperplanes. Thus we get a contribution $$ {n\choose 2}\sum_{j\geq 3}(-1)^j {n-2\choose j}t = {n\choose 2}\left[-1+(n-2)-{n-2\choose 3}\right]t. $$

Case 4: $e=0$. (a) Any three hyperplanes intersect at a point, except when all three contain the same two points $p,q\in X$. There are ${{n\choose 3}\choose 3}$ ways to choose three hyperplanes, and ${n\choose 2}{n-2\choose 3}$ ways to choose them so that they intersect in two points of $X$. Hence we get a contribution $$ -\left[ {{n\choose 3}\choose 3}-{n\choose 2}{n-2\choose 3} \right] $$ to the constant term of $\chi(t)$ (the minus sign because the number of hyperplanes is odd).

(b) Any $j\geq 4$ hyperplanes meeting at a point $p\in X$. We can choose $p$ in $n$ ways. We then must choose $j$ two-element subsets of $X-p$ whose intersection is empty. There are ${{n-1\choose 2}\choose j}$ ways to choose $j$ two-element subsets of $X-p$. If their intersection is nonempty, then they have a common element $q$ which can be chosen in $n-1$ ways, and then we can choose the remaining elements in ${n-2\choose j}$ ways. This gives the contribution $$ n\sum_{j\geq 4}(-1)^j\left[ {{n-1\choose 2}\choose j}- (n-1){n-2\choose j}\right] $$ $$ \ = n\left[ -1+{n-1\choose 2}-{{n-1\choose 2}\choose 2} + {{n-1\choose 2}\choose 3}-(n-1)\left(-1+(n-2) -{n-2\choose 2}+{n-2\choose 3}\right)\right]. $$

(c) Any $j\geq 3$ hyperplanes meeting at $p,q\in X$, together with one additional hyperplane not containing $p$ or $q$. There are ${n\choose 2}$ choices for $p,q$ and ${n-2\choose j}$ ways to choose $j$ hyperplanes containing $p,q$. There are then ${n-2\choose 3}$ ways to choose the additional hyperplane not containing $p$ or $q$. Thus we get the contribution $$ -\left[ \sum_{j\geq 3}(-1)^j{n-2\choose j}\right] {n-2\choose 3} $$ $$ -{n-2\choose 3}{n\choose 2}\left[-1+(n-2)-{n-2\choose 2} \right]. $$

Putting all this together gives the characteristic polynomial $$ t^3-{n\choose 3}t^2+ \frac{1}{72}n(n-1)(n-3)(n^3-2n^2-16n+68)t $$ $$ -\frac{1}{1296}n(n-2)(n-3)(n^6-4n^5-74n^4+698n^3-2129n^2 +2276n-120). $$ The number of regions is $$ \frac{1}{1296}(n-2)(n^8-7n^7-62n^6+938n^5-4295n^4+8429n^3 -4932n^2-2016n-648). $$ The number of bounded regions is $$ \frac{1}{1296}(n-1)(n-2)(n-3)(n^6-3n^5-77n^4+603n^3 -1508n^2+1056n+216). $$ Conceivably there could be an error in the computation, but I checked it for $n=4,5$ by a brute force computation.

This method should extend to any $d$, but the computation will be more complicated, and I am too lazy to work out the details.

$\endgroup$
3
  • 1
    $\begingroup$ A note on the stronger condition required, here is an example of what can go wrong: Consider the simple case $6$ points in the plane, no $3$ on a line. There is a special degenerate case where we can partition the $6$ points into three pairs $(A, A')$ $(B, B')$ and $(C,C')$ where the lines $AA'$, $BB'$, and $CC'$ all intersect at a point. This will have one less region than the general case. $\endgroup$
    – Nate
    Feb 19, 2020 at 20:54
  • 1
    $\begingroup$ Theorem 2.2 of Ardila-Billey arxiv.org/abs/math/0605598 gives a combinatorial description of the relevant matroid (described dually, as the intersections of generic hyperplanes rather than the spans of generic points). I don't see an easy way to extract the characteristic polynomial from it, but maybe you do. $\endgroup$ Feb 20, 2020 at 4:32
  • $\begingroup$ I replicated your result for $d=2$ based on my answer below. I proved there that $x$ generic lines produce $2x$ unbounded regions and $(x-2)(x-1)/2$ bounded ones. Then replaced $x$ with $n(n-1)/2$. Last, at each of the $n$ points the bounded regions that would exist in a generic $(n-1)$-lines case are collapsed to a point. So the total number of regions collapsed to a point is $n(n-3)(n-2)/2$. This leaves $(x-2)(x-1)/2$-$n(n-3)(n-2)/2$ bounded regions, which matches your calculation. I think $d=3$ could be tacked in a similar way, but much more messy. $\endgroup$ Feb 29, 2020 at 19:48
3
$\begingroup$

Perhaps it is worth quoting this theorem, even though it does not distinguish bounded from unbounded cells, and is phrased in terms of the number of hyperplanes rather than the number of points determining the hyperplanes.

Theorem. Let $H$ be a set of $n$ hyperplanes in $\mathbb{R}^d$. The maximum number of $k$-dimensional cells in the arrangement ${\cal A}(H)$ formed by $H$, for $0 \le k \le d$, is $$ \sum_{i=0}^k \binom{d-i}{k-i} \binom{n}{d-i} \;.$$ The maximum is attained exactly when ${\cal A}(H)$ is simple.

An arrangement is simple if every $d$ hyperplanes meet in a point, and no $d+1$ hyperplanes have a point in common. In the OP's situation, the arrangement is non-simple. For example, in $d=2$, $4$ points determine $6$ lines, but each point has $3$ lines through it.

For $d=2$ and $k=2$, the above equation reduces to the familiar expression $$\binom{n}{2} + \binom{n}{1} + \binom{n}{0} = \frac{1}{2}( n^2 + n + 2) \;.$$


Handbook of Discrete and Computational Geometry, 3rd ed. Chapman and Hall/CRC, 2017. CRC link. Chapter 28, Thm.28.1.1, p.724.

$\endgroup$
2
$\begingroup$

This non-answer completes Joseph O'Rourke's nice non-answer, for the case of $n$ hyperplanes in $\mathbb{R}^d$ in general position. But it also suggests that the OP situation may also well have unique answers.

Define:

$U_{d,n}=$ number of unbounded regions cut by $n$ hyperplanes in $\mathbb{R}^d$

$B_{d,n}=$ number of bounded regions

$T_{d,n}=$ total number of regions $=U_{d,n}+B_{d,n}$

$S_{d,n}=$ number of regions cut on the sphere $S^d$ by $n$ great $S^{d-1}$-circles

Then $U_{d,n}, B_{d,n}$, $T_{d,n}$ and $S_{d,n}$ are unique with these formulas:

$U_{d,0}=1$, $\quad B_{d,0}=0$, $\quad T_{d,0}=1$, $\quad S_{d,0}=1$

$U_{1,n}=2$, $\quad B_{1,n}=n-1$, $\quad T_{1,n}=n+1$, $\quad S_{1,n}=2n$

and for $n>0$

  1. $U_{d+1,n}=S_{d,n}$
  2. $S_{d,n}=U_{d,n}+2B_{d,n}$
  3. $T_{d,n+1}=T_{d,n}+\sum_{i=0}^{i=d-1}{n\choose i}$

Proof.

  1. In $\mathbb{R}^{d+1}$ take a huge and growing $S^d$ sphere, so that all the bounded regions zoom down to a point at the center of the sphere, the hyperplanes become great circles on the sphere and the unbounded regions corresponds to regions cut by the circles on the sphere. Therefore if the numbers are unique (as will be proved at the end) 1. follows.

  2. Centrally project $\mathbb{R}^d$ onto a half $S^d$ (tangent to it). Complete the semisphere to a sphere by central symmetry. Then the hyperplanes become great circles, the $B_{d,n}$ bounded regions in $\mathbb{R}^d$ become $2B_{d,n}$ regions in $S^d$ and the $U_{d,n}$ unbounded ones become $U_{d,n}$ regions stretching across the suture line (equator) of the sphere. Again by unicity 2. follows.

  3. Start with $\mathbb{R}^d$ and $n$ hyperplanes in generic position inside it. Now add a new hyperplane in generic position the following way: first chose a point inside one region: no matter how that point is eventually stretched to a hyperplane, to it will split the region in two, for a gain of 1, or $n \choose 0$. Now stretch that point to a line: since it is a generic line it will meet each of the $n$ hyperplanes once and at each meeting the line will cross into one one new region and split it - with a gain of $n \choose 1$ new regions. Next stretch the line to a generic 2-plane, which will meet once each of the $(d-2)$-dimensional intersections of two hyperplanes; at each meeting the growing plane will arrive from having already crossed 3 of the 4 regions, to cross into the fourth and cut it; this a gain of another $n \choose 2$ regions. In general as a generic $m-1$-plane grows to a generic $m$-plane it will meet all the $n \choose m$ $(n-m)$-dimensional intersections of $m$ hyperplanes, and each time it will go from cutting $2^m-1$ regions before crossing the intersection to cutting all $2^m$ after crossing, for a total gain of $n \choose m$ regions. This continues up to $m=d-1$, proving 3.

Proof of Unicity.

By induction:

$U_{d,0}$, $\quad B_{d,0}$, $\quad T_{d,0}$, $\quad S_{d,0}$ are unique;

$T_{d,n}$ unique $\implies$ $T_{d,n+1}$ unique (by the proof of 3.);

$U_{d,n}$ and $B_{d,n}$ unique $\implies$ $S_{d,n}$ unique (by the proof of 2. and the fact that the construction can be reversed in a non-unique way to show that $S_{d,n}=U_{d,n}+2B_{d,n}$ for some values of $U_{d,n}$ and $B_{d,n}$);

$S_{d,n}$ unique $\implies$ $U_{d+1,n}$ unique (by the proof of 1.);

$U_{d+1,n}$ and $T_{d+1,n}$ unique $\implies$ $B_{d+1,n}$ unique (as $B=T-U$).

$\endgroup$
1
  • 1
    $\begingroup$ I have a feeling that jiggling the $n \choose d$ hyperplanes of the OP into generic positions while carefully keeping track of the corresponding increase of regions (both bounded and unbounded) one may be able to reach an answer to the OP's question too. For a start this should be relatively easy for $d=2$ (but I haven't done it). $\endgroup$ Feb 23, 2020 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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