We study the worst case complexity of computing c-approximations of surface
integrals. This problem has two sources of partial information: the integr
and 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 scal
ar function of I variables, and g is an s times continuously differentiable
injective function of d variables with I components. We must have d less t
han or equal to l and s greater than or equal to 1 for surface integration
to be well-defined. Surface integration is related to the classical integra
tion problem for functions of d variables that are min{r, s - 1} times cont
inuously differentiable, This might suggest that the complexity of surface
integration should be Theta((1/epsilon)(d/min{r, s})). Indeed, this holds w
hen d < l and s = 1, in which case the surface integration problem has infi
nite complexity. However, if d less than or equal to l and s greater than o
r equal to 2, we prove that the complexity of surface integration is O((1/e
psilon)(d/min{r, s})). Furthermore, this bound is sharp whenever d < l. (C)
2001 Academic Press.