Algebraic curve intersecting square-grid Let us subdivide the unit square into square-grid cells with sidelength $w$. This will give us roughly $w^{-2}$ cells.
Formally 
$$  g_{ij} = \{(wi, wj) + (x,y) : 0\leq x,y\leq w \},$$
for $i,j = 0,\ldots, 1/w -1$.
Now consider an algebraic curve $c$, described by $p(x,y) = 0$ of degree
at most $\Delta$. 
How many grid cells does $c$ intersect at most as a function of $w$ and $\Delta$?
 A: First consider algebraic curves that are not self-crossing. Let $n:=1/w$. The graph of a monotone function $y=f(x)$ can intersect at most $2n$ grid cells since (for weakly increasing $f$) any cell can only be followed by the cell to its north or to its east. So to bound the  number of cells that the given curve ${\bf c}=\{(x,y): p(x,y)=0\}$ intersects, it suffices to partition ${\bf c}$ into monotone sections. By the implicit function theorem, any connected part of the curve where the ratio of partial derivatives 
$\partial_y(p)/\partial_x(p)$ is well defined and of a fixed sign, can be represented by a monotone function.
If ${\bf c}$ is not self crossing, the number of monotone sections is  at most one larger than the number of points where at least one of the partial derivatives $\partial_y(p)$ and $\partial_x(p)$ vanishes. By Bezout's theorem (see e.g. [1]) the number of common zeros of $p$ and $\partial_y(p)$ is at most $\Delta(\Delta-1)$, so (discarding a lower order term), the number of monotone sections is at most $2\Delta^2$, yielding an upper  bound of 
$4\Delta^2 n$ for the number of grid cells that such a non-self-crossing algebraic curve can intersect. 
Once we allow self-crossing, the same method still applies: 
the number of self-crossings is classically bounded by intersecting the curve with a  translate and applying Bezout. See [2], though a more detailed reference would be useful.
If you remove all points of self intersections as well as points where one of the partial derivatives of $p$ vanishes, the number of components obtained is still $O(\Delta^2)$ which implies an upper bound of $O(\Delta^2 n)$ for the number of grid cells that  a degree $\Delta$ plane algebraic curve can intersect. 
For curves that can be expressed as $y=F(x)$ where $F$ is a degree $\Delta$ polynomial, the same argument yields an upper bound of $O(\Delta n)$ for the number of grid cells intersected.
[1] https://terrytao.wordpress.com/tag/bezouts-theorem/
[2] https://en.wikipedia.org/wiki/Intersection_theory#Self-intersection 
A: Let's assume that the cells are open, i.e. a curve intersects a cell only if it has a point in its interior.  Let's also assume that the curve $p(x,y)=0$ is smooth. Set $\omega=\frac{1}{n}$. Assuming all this, one can get the following upper bound on the number of intersected cells:
$$(\Delta^2-3\Delta+4)/2+ \Delta(2n+2).$$
Note that the first term is always smaller than the second one if we consider only the case $\Delta\le n$. Otherwise, you can take a curve that intersects all the cells - namely a union of $\Delta$ vertical lines.
Proof. Let me first explain the first term. This is the maximal number of connected components of a real algebraic curve given by Harnack's curve theorem.
https://en.wikipedia.org/wiki/Harnack%27s_curve_theorem
In particular, there could be some cells that completely contain connected components of the curve $p(x,y)=0$.
Let us now concentrate on cells such that the curve $p(x,y)=0$ intersects their boundary. After making a small translation $(x,y)\to (x+\varepsilon_1, y+\varepsilon_2)$ we can assume that the curve $p(x,y)=0$ intersects all $2n+2$ horizontal and vertical lines transversely. We can also assume that it avoids the grid of $(n+1)^2$ points $(n_1/n, n_2/n)$. I claim now that  the number of cells whose boundary is intersected by $p(x,y)=0$ is at most $2\Delta(2n+4)$.
Indeed, consider the intersection of $p(x,y)=0$ with the $1\times 1$ square. It has two types of connected components: circles that are contained in the square and segments that join two points on the boundary of the square. For each circle, it is clear that the number of cells that it intersects is at most the number of its intersections with $2n+2$ vertical and horizontal lines. For each segment, this number is at most the (number of intersections with $2n+2$ vertical and horizontal lines)$-1$. 
So we just need to bound the number of intersections of $p(x,y)=0$ with $2n+2$ lines. Clearly this is at most $\Delta(2n+2)$.
QED. 
Remark. This upper bound is not quite sharp when $\Delta$ is getting large. But is not so bad either, for example, there is an obvious lower bound $n\Delta$ and in the case when $\Delta$ is small, one can construct a curve that intersects approximately $2n\Delta-\Delta^2$ cells. Just take a collection of lines parallel to a diagonal of the square. 
