What Is the Complexity of Surface Integration?

✍ Scribed by A.G. Werschulz; H. Woźniakowski

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 179 KB
• Volume: 17
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.2001.0578

✦ Synopsis

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 3((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.