2001 Reports

Surface Approximation May Be Easier Than Surface Integration

Werschulz, Arthur G.; Wozniakowski, Henryk

The approximation and integration problems consist of finding an approximation to a function f or its integral over some fixed domain 6. For the classical version of these problems, we have partial information about the functions f and complete information about the domain 6; for example, 6 might be a cube or ball in R d . When this holds, it is generally the case that integration is not harder than approximation; moreover, integration can be much easier than approximation. What happens if we have partial information about 6? This paper studies the surface approximation and surface integration problems, in which 6 = 6g for functions g. More specifically, the functions f are r times continuously differentiable scalar functions of l variables, and the functions g are s times continuously differentiable 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 Lq - sense. These problems are well-defined, provided that d ≤ l, r ≥ 0, and s ≥ 1. Information consists of function evaluations of f and g. We show that the ε-complexity of surface approximation is proportional to (1/ε) 1/µ with µ = min{r,s}/d. We also show that if s ≥ 2, then the ε-complexity of surface integration is proportional to (1/ε) 1/ν with ν = min r d , s − δs,1(1 − δd,l) min{d, l − 1}. (This bound holds as well for several subcases of s = 1; we conjecture that it holds for all r ≥ 0, s ≥ 1, and d ≤ l.) Using these results, we determine when surface approximation is easier than, as easy as, or harder than, surface integration; all three possibilities can occur. In particular, we find that if r = s = 1 and d < l, then µ = 1/d and ν = 0, so that surface integration is unsolvable and surface approximation is solvable; this is an extreme case for which surface approximation is easier than surface integration.