Approximating the volume of unions and intersections of high-dimensional geometric objects (Q982950): Difference between revisions

The problem of the efficiency of computing the volume of unions and intersections of \(n\) bodies in a \(d\)-dimensional space is studied for different kinds of bodies: boxes, spheres, polytopes, convex bodies determined by an oracle and schlicht domains. All these bodies are allowed together with some of their affine transformations which support the following queries in polynomial time: point query means that one can test whether a given point lies inside the object, sample query means that one can sample a point uniformly and volume query means that one can calculate the volume of the object. A fast FPRAS is constructed for computing the volume of unions of objects answering these queries, even in a relaxed manner. It is shown that this algorithm is an FPRAS for the computation of the volume of the union of convex bodies. The similar problem for intersection of high-dimensional geometric objects has, in some cases, a negative answer. It is shown that there is no multiplicative polynomial-time \(2^{d^{1-\epsilon}}\)-approximation in general, unless NP = BPP by identifying a hard sub-problem. An additive \(\epsilon\)-approximation is given instead. The runtime is estimated in each case.