1999 Reports

# What is the complexity of surface integration?

We study the worst case complexity of computing ε-approximations of surface integrals. This problem has two sources of partial information: the integrand f and the function g defining the surface. The problem is nonlinear in its dependence on g. Here, f is an r times continuously differentiable scalar function of l variables, and g is an s times continuously differentiable injective function of d variables with l components. We must have d ≤ l and s ≥ 1 for surface integration to be well-defined. Surface integration is related to the classical integration problem for functions of d variables that are min{r,s − 1} times continuously differentiable. This might suggest that the complexity of surface integration should be 2((1/ε)d/ min{r,s−1} ). Indeed, this holds when d < l and s = 1, in which case the surface integration problem has infinite complexity. However, if d ≤ l and s ≥ 2, we prove that the complexity of surface integration is O((1/ε)d/ min{r,s} ). Furthermore, this bound is sharp whenever d < l.

## Subjects

## Files

- cucs-004-99.pdf application/pdf 123 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-004-99
- Published Here
- April 21, 2011