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
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.
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) \;.$$
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$
Proof.
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.
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.
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$).
