Source-linked AI summary
Approximating the volume of unions and intersections of high-dimensional geometric objects
Karl Bringmann, Tobias Friedrich
TL;DR
The paper asks how efficiently volumes of unions and intersections of high-dimensional geometric objects can be computed despite exact counting hardness. It gives an FPRAS for unions using three possibly weak oracles, while proving strong inapproximability and an additive approximation result for intersections. These results cover important geometric volume problems, including Klee’s Measure Problem, within the stated oracle and object-class assumptions.
Problem
Exact union and intersection volume computation is hard in high dimensions, including for boxes, motivating approximation methods for these geometric counting problems.
Method
The paper combines an FPRAS based on point-membership, volume, and sampling oracles with uniform sampling from a minimum-volume body for additive intersection estimation.
Results
The union volume admits an FPRAS under weak oracle access, whereas intersections have no multiplicative approximation for certain boxes but do admit a polynomial-time additive ε-approximation.
Takeaways & Limitations
Klee’s Measure Problem and related union-volume problems can be approximated efficiently under the oracle conditions, while intersection volumes have a substantially narrower approximation guarantee.
Takeaways & Limitations
The union FPRAS requires polynomial-time point-membership, volume, and sampling oracles, and the intersection guarantee is additive rather than multiplicative.
Abstract
from arXiv · showhide
We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove #P-hardness for boxes and show that there is no multiplicative polynomial-time $2^{d^{1-ε}}$-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time $ε$-approximation.
1 Introduction
The paper studies the computational difficulty of volumes of unions and intersections in high dimensions, showing exact union volume is #P-hard while approximation is feasible under three weak oracle capabilities. It develops an FPRAS for unions and establishes strong hardness and additive approximation results for intersections.
- Problem and motivation: #P-hardness makes exact volume computation for unions intractable for classes containing axis-parallel boxes unless P = NP.This motivates approximation algorithms for union volumes.
- Union-volume approximation: The union-volume FPRAS applies to bodies supporting point-membership, volume, and uniform-sampling queries in polynomial time.The supported classes include boxes, spheres, polytopes, oracle-defined convex bodies, schlicht domains, and fixed affine transformations.
- Union-volume approximation: All three oracle requirements may be weak, allowing approximate membership, approximate volume, and almost-uniform sampling.The weak-query model permits controlled errors in each oracle rather than requiring exact operations.
- Union-volume approximation: The FPRAS runs in polynomial time in the oracle runtimes and has a specialized bound for boxes, including Klee’s Measure Problem.For boxes, the general runtime expression reduces to a simpler bound stated in the paper.
2 Volume computation of unions
The paper proves union-volume computation is #P-hard even for axis-parallel boxes, then gives an FPRAS for bodies supporting point, volume, and sampling queries, including weak approximate oracles.
- 2.1 Computational complexity of union calculations: Klee’s Measure Problem is #P-hard, so exact union-volume computation for classes containing axis-parallel boxes is intractable unless P = NP.The reduction counts satisfying assignments of monotone CNF formulas through unions of boxes.
- 2.1 Computational complexity of union calculations: The hardness extends to unions of boxes sharing the origin, covering the hypervolume indicator used for Pareto-set fitness.Thus the result applies to a specific optimization measure as well as KMP.
- 2.2 Approximation algorithm for the volume of unions: ApproxUnion estimates union volume using PointQuery, VolumeQuery, and SampleQuery, adapting an FPRAS strategy for #DNF to continuous bodies.It samples bodies roughly by volume, samples points, and estimates coverage through repeated membership queries.
- 2.3 Classes of objects supported by our FPRAS: Boxes support all three oracles exactly in O(d), yielding an FPRAS for KMP; the framework also covers generalized box-spheres, convex bodies, and certain schlicht domains.For convex bodies, the result gives an FPRAS with a stated O*(n^3d^3/ε^2)-type runtime bound.
- 2.2 Approximation algorithm for the volume of unions: The algorithm remains valid when all three oracles are weak, provided their errors satisfy explicit accuracy conditions.For sufficiently small errors, Lemma 3 establishes the required condition and polynomial query complexity.
- 2.4 Analysis of our algorithm: With exact oracles, the approximation condition becomes trivial and ApproxUnion is an FPRAS, whereas nonzero oracle errors impose a lower bound on attainable accuracy.The paper notes that arbitrary accuracy is impossible when query answers are inaccurate.
3 Volume computation of intersections
Intersection-volume computation can be substantially harder than union-volume computation: exact computation is #P-hard, strong multiplicative approximation is ruled out for certain boxes, but additive approximation remains efficient.
- Intersection-volume computation can be harder than union-volume computation, and randomized approximation may be impossible for many geometric-object classes.
- The exact volume of intersections of general boxes is #P-hard because polytopes can be represented as intersections of halfplanes encoded by boxes.
- Membership-oracle methods for convex-body volume cannot directly approximate intersections because the intersection may lack a known interior point or inscribed sphere.
- Co-boxes are complements of corner-cut boxes within [0,1]^d, and their intersection encodes satisfying assignments of a monotone CNF formula.
- 2^{d^{1−ε}}-factor approximation is impossible for the relevant intersection volumes unless NP=BPP.The reduction uses the fact that the intersection volume multiplied by 2^d equals the number of satisfying assignments.
- An additive ε-approximation is obtained by uniformly sampling from the smallest-volume input body and estimating the fraction of samples lying in every body.The resulting error is relative to the minimum input volume, not necessarily to the potentially much smaller intersection volume.
4 Discussion and open problems
The paper establishes strong hardness and approximation boundaries for unions and intersections, while leaving deterministic union approximation and convex-body intersection hardness open.
- Exact union volume is #P-hard for classes containing axis-parallel boxes.
- The union problem has an FPRAS under three weak oracle conditions, including approximate membership, sampling, and volume queries.
- No deterministic approximation is currently established for a non-trivial class of unions, and constant-factor deterministic approximation for KMP remains open.
- For intersections, no deterministic or randomized multiplicative approximation is possible for co-boxes, while a simple additive approximation is available.
- For every fixed ε > 0, approximating the volume within 2^(d^(1−ε)) is NP-hard.
- The intersection results correspond to the discrete approximability of #DNF and inapproximability of #SAT.