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?

Improve this question
$\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
    Commented May 29, 2018 at 23:57
  • $\begingroup$ Yes this is correct. $\endgroup$
    – Christian Chapman
    Commented 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$
    – Mark L. Stone
    Commented 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$
    – Christian Chapman
    Commented 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
    Commented May 30, 2018 at 0:40

0

Reset to default

You must log in to answer this question.