What is the complexity of volume calculation?

Werschulz, Arthur G.; Wozniakowski, Henryk

We study the worst case complexity of computing ε-approximations of volumes of d-dimensional regions g([0, 1]d ), by sampling the function g. Here, g is an s times continuously differentiable injection from [0, 1]d to R d , where we assume that s ≥ 1. Since the problem can be solved exactly when d = 1, we concentrate our attention on the case d ≥ 2. This problem is a special case of the surface integration problem studied in [12]. Let c be the cost of one function evaluation. The results of [12] might suggest that the ε- complexity of volume calculation should be proportional to c(1/ε) d/s when s ≥ 2. However, using integration by parts to reduce the dimension, we show that if s ≥ 2, then the complexity is proportional to c(1/ε) (d−1)/s . Next, we consider the case s = 1, which is the minimal smoothness for which our volume problem is well-defined. We show that when s = 1, an ε-approximation can be computed with cost proportional to at most c(1/ε) (d−1)d/2 . Since a lower bound proportional to c(1/ε) d−1 holds when s = 1, it follows that the complexity in the minimal smoothness case is proportional to c(1/ε) when d = 2, and that there is a gap between the lower and upper bounds when d ≥ 3.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-024-00
Published Here
April 21, 2011