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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-018-01
Published Here
April 22, 2011