What is the complexity of volume calculation?
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 . Let c be the cost of one function evaluation. The results of  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.
- cucs-024-00.pdf application/pdf 127 KB Download File
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