Intersections of algebraic surfaces with hypercubes of a $d$-dimensional grid This is a follow-up question, to a question I asked earlier.
See Algebraic curve intersecting square-grid.
Consider $n^d$ unit hypercubes in $d$-dimensional Euclidean space
tightly packed in the canonical way. 
Let $f \in \mathbb{Z}^d$ be a vector,
then we define the hypercube $c_f$ as
$$ c_f = \{ f + x \in \mathbb{R}^d : 0\leq x_i \leq 1, \forall i =1,\ldots,d\} $$
We consider all hypercubes with $1\leq f_i\leq n$.
Let us now consider a polynomial $p$ in $d$ variables 
with maximum degree $\Delta$.
How many hypercubes can $p$ intersect, in terms of $\Delta$, $n$ and $d$?
(We say $p$ intersects a set $S$ if $\exists \ x \in S : p(x) = 0$.)
 A: Let us start with the case $d = 1$. In this case, we have a univariate polynomial $p(x)$
and we ask how many unit intervals it can hit at most. 
The answer $\Delta$ is well known.
Now we tackle the case $d = 2$, for pedagogical purposes.
Let us assume that $c = \{ x\in \mathbb{R}^2: p(x) = 0\}$ has only one connected component. 
(Here is a gap in the argument, that we don't want to fill for the moment.)
Note that $c$ is a one-dimensional object and we can think of $c$ as going in and out
of a component. So whenever $c$ does this, we visited one more component.
In two dimensions, our cubes are bounded by $n+1$ horizontal and vertical lines.
It is sufficient to count the number of times such a line is hit.
Now the set $c \cap \ell$, for a line $\ell$ can be described by a 
univariate polynomial of max degree $\Delta$. Thus by the case $d=1$,
each line is intersected at most $\Delta$ times.
This gives an upper bound of $(2n+2)(\Delta) \leq 3n\Delta$.
(We assume $n\geq 2$.)
See also the answer of Dmitri Panov 
(Algebraic curve intersecting square-grid)
Now let us go to the general induction step $(d-1) \rightarrow d$.
Again, let us assume that $c = \{ x\in \mathbb{R}^2: p(x) = 0\}$ has only one connected component. 
All the hypercubes are bounded by $dn+d$ hyperplanes. Every intersection
of $c$ to a hypercube is witnessed by an intersection of $c$ to at least
one of the hyperplanes. 
Now consider one of the hyperplanes $H$ and consider the induced grid arrangement $A$
on $H$.
By induction, at most $(d-1)!(n+1)^{d-2}\Delta$ of the cells of $A$ are visited by $c$.
Thus in total among all the hyperplanes at most 
$(dn+d) \cdot (d-1)!(n+1)^{d-2}\Delta \leq d!(n+1)^{d-1}\Delta$
of the induced cells are touched by $c$.
(We assume $n\geq 2$.)
Thus also at most $3n^{d-1}\Delta$ full dimensional cubes 
are visited by $c$. 
Additionally, if $c$ has more components, some of the components are completely contained in some of the hypercubes. But the number of components is bounded by a function of $\Delta$ and $d$ and independent of $n$.
So the answer will be $d!(n+1)^{d-1}\Delta + f(d,\Delta)$.
Remark: We have to take care of the $f(d,\Delta)$ also in the induction step. 
:(. This proof is not complete yet. It would be nice to absorb it somehow in the first term.
