Number of polytopes formed by connecting points on a hypercube 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.)
 A: 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.
A: Here is $a(3,2)$, which confirms Gerhard's count of $340$
regions:

     


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


*

*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,


*

*Every $x\in L$ has the vector form $(x_1,x_2,...,x_{d+1})$.

*For every coordinate we have $n+1$ choices of possible values.

*Choices are independent, so we multiply by $n+1$ for every coordinate.

*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.  
