In the book Lecture Notes on Discrete Geometry by Jirka Matousek, in page 127, a theorem is proved:

The number of cells ($d$-faces) in a simple arrangement of $n$ hyperplanes in $\mathbb{R}^d$ equals $\Phi_d(n)=\sum_{0\leq i\leq d}\binom{n}{i}$.

They prove it for $n=d=1$, assume the equation for dimension $d$ with $n-1$ hyperplanes. The step I don't understand is:

Since we assume general position, the $n-1$ previous hyperplanes divide the newly inserted hyperplane $h$ into $\Phi_{d-1}(n-1)$ cells by the inducative hypothesis.

Why is it true?


  • For a finite set of hyperplanes $H$ in $\mathbb{R}^d$, the cells of $H$ are the connected components of $\mathbb{R}^d \setminus \bigcup H$.
  • $H$ is in a simple arrangement if and only if $H$ is in a general position, which means that the intersection of every $2\leq k\leq d+1$ hyperplanes is $d-k$-dimensional.
  • 1
    $\begingroup$ A question to fill a gap in my knowledge. The last sentence seems to imply the empty subspace, which we get as an intersection of $k=d+1$ hyperplanes in a generał position, has dimension $-1$. Is it correct? Just curious, I've never seen a dimension assigned to an empty space. $\endgroup$ – CiaPan Apr 18 at 6:15
  • $\begingroup$ @CiaPan I have wondered about it too, I guess that dimension of $-1$ means the empty set. $\endgroup$ – J. Doe Apr 18 at 9:28
  • $\begingroup$ Please see the expanded answer. $\endgroup$ – CiaPan Apr 18 at 10:00

Apparently the part you quote explains an inductive step over $n$, a number of hyperplanes.

Consider a 2D case first: in a general configuration the $n$-th line (1D hyperplane) intersects $n-1$ previous lines and those points (zero-dimensional) of intersections dissect the line into $n$ segments - 1D cells. Each of those segments corresponds to some polygonal cell on the plane, defined by the previous $n-1$ lines, and it dissects that polygon into two. So when constructing the configuration by adding lines, the $n$-th increment in the number of 2D cells of the plane equals the $(n-1)$-st number of 1D cells.

Then 3D: the number of solids - 3D cells in a space, added by the $n$-th 2D plane equals a number of 2D polygonal cells defined by $n-1$ lines - 1D intersections of the plane with previous planes. Each of those polygons corresponds to a single polyhedral cell of the 3D space, which becomes dissected into two by the $n$-th plane.

And generally, when you add the $n$-th, $(d-1)$-dimensional hyperplane to a configuration of $n-1$ hyperplanes in a $d$-dimensional space, you get on the new hyperplane a configuration of $n-1$, $(d-2)$-dimensional intersections with previous hyperplanes. Then each of $\bbox[lightgray]{\Phi_{d-1}(n-1)}$ cells on the $n$-th hyperplane dissects one cell in the $d$-dimensional space into two, adding $1$ to a number of cells. Hence $$\Phi_d(n) = \Phi_d(n-1) + \bbox[lightgray]{\Phi_{d-1}(n-1)}$$


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.