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...
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
