Consider a convex function $f$ defined on a $d$-dimensional hypercube $[0,1]^d$. Now for fixed $m \in \mathbb{N}$, consider the grids $\mathcal{G}\_m=\{(i\_1/m,\cdots,i\_d/m)\}$ where $i\_\alpha\in\{0,1,\cdots,m\}$ for all $\alpha$, and do linear interpolation of $f$ on these grids to get a piecewise affine function $\bar{f}$ on $[0,1]^d$. My question is, assuming enough curvature for $f$, how many affine pieces are there for $\bar{f}$? I would guess an answer on the order of $O(m^d)$, but it would be good if there is any known results/references...



number of affine pieces of linear interpolation of convex functions in high dimension
Let's think of choosing the values of $f$ at the grid points one grid point at a time, in such a way that the result is convex. 


If you work systematically through the grid points in an order so that each time you add a lattice point it is outside the convex hull of the lattice points you have already added, then you can preserve convexity by taking the value of $f$ at that point to be any point lower than the value at that grid point determined by any of the affine hyperplanes that have already been defined by any $d+1$ of the other points. This further guarantees that for each grid point you will get at least one new facet, so at least $m^d$ facets. 


On the other hand, each facet corresponds to a region defined by (scaled) lattice points, and therefore its volume is at least $1/d!$. Thus, you won't get more than $d!m^d$ facets. 


Thus the number of facets is $O(m^d)$ (assuming you are thinking of $d$ as fixed and $m$ as increasing). 


