Academic Commons


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
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.