Number of polytopes formed by connecting points on a hypercube

Question

Fix an integer $d\geq 1$, and let $n\geq 1$. Drawing hyperplanes between all the $d$-sets of lattice points on the boundary of the hypercube $[0,n]^d\subseteq \mathbf{R}^d$ defines a partition of $[0,n]^d$ into several distinct polytopes; let $a(n,d)$ denote the number of such polytopes. (Note that $a(n,d)$ is divisible by $2^d$.) For instance, $a(1,2) = 4$ and $a(2,2) = 56$. What can be said about the sequence $a(n,d)$ as $n$ and $d$ vary? (I'd originally asked about the generating function, but this seems way too hard. I would be interested in asymptotics with $n$ or $d$ fixed.)

Answer 1

For d=2, use Euler's formula to compute these values programmatically. When ever you add a new line segment, count the edges it gets broken into, and the number of new vertices created. The end result is a planar graph whose edges you have tallied (be sure to add extra edges when creating a new vertex) and vertices, and then compute faces using the formula for a planar graph.

I imagine a similar approach is used for higher dimensions. I would ask Joseph O'Rourke about it.

Gerhard "Is This Really Computational Topology?" Paseman, 2020.04.23.

Answer 2

Here is $a(3,2)$, which confirms Gerhard's count of $340$ regions:

---

     

---

Answer 3

This is a counting problem, first we need to know a one thing:

1. How many lattice points exist on the boundary of our $L=[0,n]^d$ dimensional cube?

We only need count lattice points $x \in [o,n]^d$ such that a given coordinate $x_j \in \{0,n\}$, for some $1 \le j \le d$. This tells us $x$ lies on the boundary of $S$.

We count all lattice points and substract the internal points;

$$ Q:=|\{ x \in L | \;\; x\in \text{ surface}\}| = (n+1)^d - (n-1)^d $$

The way to reason about that count is as follows,

1. Every $x\in L$ has the vector form $(x_1,x_2,...,x_{d+1})$.
2. For every coordinate we have $n+1$ choices of possible values.
3. Choices are independent, so we multiply by $n+1$ for every coordinate.
4. There are $d$ coordinates so we get $(n+1)^d$

The reasoning behind how many inner points there are so we can subtract them is almost exactly the same, only in step 2 we have $(n+1) - 2$ choices; that is, no coordinate is allowed to be $n,0$ as that would place the point on the surface of the lattice.

Let's say, $L(n,d) := [0,n]^d$, and $$ \gamma( L(n,d) ) = |\{ A \in L(n,d) | A \text{ is a polytope as described in the question } \}| $$ then

$$\gamma(L(n,2))=\sum_{k=2}^{Q-1} \binom{Q-1}{k}= (2)^{(Q-1)}-(Q-1)-1 $$. $$\gamma(L(n,3))=\sum_{k=3}^{Q-1} \binom{Q-1}{k}= (2)^{(Q-1)}-\frac{Q(Q-1)}{2}-(Q-1)-1 $$. $$\cdots$$ $$\gamma(L(n,d))=\sum_{k=d}^{Q-1} \binom{Q-1}{k}= (2)^{(Q-1)}-\sum_{k=0}^{d-1} \binom{Q-1}{k} $$.

The origin is fixed, so we have $Q-1$ points to choose from, we may choose any number of these to form a polytope with some exceptions. For $d=2$, except 0 points, which leaves only the origin; or one point, which would make only lines. Similar for $d=3$, we may not choose just two points as this only makes a plane, and so on.

EDIT: The underlying assumption of this count is that the origin is a "corner" of every polytope.