Approximating the volume of unions and intersections of high-dimensional geometric objects

DOI10.1016/j.comgeo.2010.03.004zbMath1206.65072OpenAlexW3122481131MaRDI QIDQ982950

Karl Bringmann, Tobias Friedrich

Publication date: 28 July 2010

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.03.004

zbMATH Keywords

volumealgorithmpolytopesapproximationspheresmeasureconvex bodiesboxesKlee's measure problemintersection of geometric objectsunion of geometric objects

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Efficient optimization of many objectives by approximation-guided evolution ⋮ A box decomposition algorithm to compute the hypervolume indicator ⋮ Raychaudhuri equation in an anisotropic universe with anisotropic sources ⋮ Bi-goal evolution for many-objective optimization problems ⋮ Approximating the least hypervolume contributor: NP-hard in general, but fast in practice ⋮ Efficient transformations for Klee's measure problem in the streaming model ⋮ Multi-objective optimization with an adaptive resonance theory-based estimation of distribution algorithm ⋮ Population size matters: rigorous runtime results for maximizing the hypervolume indicator ⋮ Speeding up many-objective optimization by Monte Carlo approximations ⋮ Stochastic convergence of random search methods to fixed size Pareto front approximations ⋮ Convergence of set-based multi-objective optimization, indicators and deteriorative cycles ⋮ Implicit enumeration strategies for the hypervolume subset selection problem ⋮ Performance indicators in multiobjective optimization ⋮ Approximate set union via approximate randomization ⋮ Approximate set union via approximate randomization ⋮ Learning context-dependent choice functions ⋮ Unnamed Item ⋮ Approximate weighted model integration on DNF structures ⋮ FPBH: a feasibility pump based heuristic for multi-objective mixed integer linear programming ⋮ Practical volume approximation of high-dimensional convex bodies, applied to modeling portfolio dependencies and financial crises

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A (slightly) faster algorithm for Klee's measure problem
• Computing the volume is difficult
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• On the hardness of approximate reasoning
• Counting independent sets up to the tree threshold
• The problem of calculating the volume of a polyhedron is enumerably hard
• A note on a method for generating points uniformly on n -dimensional spheres
• Can the Measure of ∪ n 1 [ a i , b i be Computed in Less Than O(n logn) Steps?]
• Counting without sampling
• Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
• On the Complexity of Computing the Volume of a Polyhedron
• Monte-Carlo approximation algorithms for enumeration problems
• The measure problem for rectangular ranges in d-space
• New Upper Bounds in Klee’s Measure Problem
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Random walks and anO*(n5) volume algorithm for convex bodies
• Semi-Online Maintenance of Geometric Optima and Measures
• Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families