4
$\begingroup$

$C$ is the set of vectors which are coordinate-wise less than $\overline{c}\in [-1,1]^d$ and greater than $\underline{c}\in [-1,1]^d.$ Is there a procedure not exponentially complex in $d$ that computes the volume of $C\cap B(0,1)$ to arbitrary precision?

$C$ has $d$ different classes of edges and many edges of each class, so it can be very disorganized with respect to $B(0,1)$ in general. For this reason the algebraic formula for the quantity is difficult to work with directly.

The best reference I have found so far is this, which only gives a very naive randomized algorithm (monte-carlo by picking a point uniform along either the cuboid or the sphere, whichever has smaller volume): https://www.sciencedirect.com/science/article/pii/S0925772110000167

What is the state of the art for this sort of computation?

$\endgroup$
5
  • $\begingroup$ I interpret this as: if you have e.g. $\bar{c} = (c_1,\dots,c_n)$ , then the region $C$ would have $x \in C\ \Rightarrow\ x_i \leq c_i$. Similarly for being lower bounded by the components of $\underline{c}$. Is that right? $\endgroup$
    – SBK
    May 29, 2018 at 23:57
  • $\begingroup$ Yes this is correct. $\endgroup$ May 29, 2018 at 23:58
  • $\begingroup$ I don't follow. If, as suggested by the question title, $C$ is the hypercube with vertices +/- 1 and B(0,1) is the unit ball $\|x\|_2 \le 1$, then their intersection is just the unit ball. So what is wrong with my interpretation? Is $C$ wholly contained within the hypercube, but not equal to it, in which case, what can you tell us about $C$? $\endgroup$ May 30, 2018 at 0:01
  • 1
    $\begingroup$ That is only one possibility for $C$. $C$ isn't necessarily the hypercube with vertices +/-1, it is instead the hyper-rectangle bounded by the vectors $\underline{c}, \overline{c}\in \mathbb{R}^d$, each component of the two vectors in the range $[-1,1]$. $\endgroup$ May 30, 2018 at 0:04
  • 3
    $\begingroup$ he obvious idea would be to approximate the characteristic function of $[e^{-1},1]$ by a polynomial $\sum c_k x^k$ and say that the characteristic function of the unit ball is just $\sum c_k e^{-k|x|^2}$. The integral of a Gaussian over a cuboid is a piece of cake and the approximation is not hard but keep in mind that the coefficients are huge (exponential in $d$), so you need to use arbitrary precision arithmetic and to find a way to compute $Erf()$ to arbitrary precision in decent time near infinity (otherwise you'll be outputting total garbage). Does anybody know how to do the latter? $\endgroup$
    – fedja
    May 30, 2018 at 0:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.