Surface Approximation Is Sometimes Easier than Surface Integration

The approximation and integration problems consist of finding anapproximation to a function $f$ or its integral over some fixeddomain $\Sigma$. For the classical version of these problems, wehave partial information about the functions $f$ and completeinformation about the domain $\Sigma$; for example, $\Sigma$ might bea cube or ball in $\reals^d$. When this holds, it is generally thecase that integration is not harder than approximation; moreover,integration can be much easier than approximation. What happens if wehave partial information about $\Sigma$? This paper studies thesurface approximation and surface integration problems, in which$\Sigma=\Sigma_g$ for functions $g$. More specifically, thefunctions $f$ are $r$ times continuously differentiable scalarfunctions of $l$ variables, and the functions $g$ are $s$ times continuouslydifferentiable injective functions of $d$ variables with$l$ components. The class of surfaces considered is generated as images of cubes or balls, or as oriented cellulated regions.Error for the surface approximation problem is measured in the $L_q$-sense.These problems are well defined, provided that $d\le l$, $r\ge 0$, and$s\ge 1$. Information consists of function evaluations of $f$ and $g$.We show that the $\e$-complexity of surfaceapproximation is proportional to $(1/\e)^{1/\mu}$ with $\mu=\mrs/d$.We also show that if $s\ge 2$, then the $\e$-complexity of surfaceintegration is proportional to $(1/\e)^{1/\nu}$ with$\nu=\min\left\{\frac{r}{d},\frac{s-\delta_{s,1}(1-\delta_{d,l})}{\min\{d,l-1\}}\right\}.$(This bound holds as well for several subcases of $s=1$; we conjecturethat it holds for all $r\ge0$, $s\ge1$, and $d\le l$.) Using theseresults, we determine when surface approximation is easier than, aseasy as, or harder than, surface integration; all three possibilitiescan occur. In particular, we find that if $r=s=1$ and $d