Computing the volume is difficult
From MaRDI portal
Publication:1093369
DOI10.1007/BF02187886zbMath0628.68041OpenAlexW2044142947WikidataQ59410508 ScholiaQ59410508MaRDI QIDQ1093369
Publication date: 1987
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02187886
Analysis of algorithms and problem complexity (68Q25) Inequalities and extremum problems involving convexity in convex geometry (52A40) Other problems of combinatorial convexity (52A37)
Related Items (44)
Approximating the volume of convex bodies ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Concentration phenomena in high dimensional geometry ⋮ A note on approximation of a ball by polytopes ⋮ Stochastic Billiards for Sampling from the Boundary of a Convex Set ⋮ Multivariate volume, Ehrhart, and \(h^\ast \)-polynomials of polytropes ⋮ On best \(m\)-term approximations and the entropy of sets in the space \(L^ 1\) ⋮ Some more n‐dimensional geometry† ⋮ Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume ⋮ Contextual Search via Intrinsic Volumes ⋮ Tropical Monte Carlo quadrature for Feynman integrals ⋮ Sampling dynamic networks with application to investigation of HIV epidemic drivers ⋮ Theorems of Carathéodory, Helly, and Tverberg without dimension ⋮ Convex geometry and its applications. Abstracts from the workshop held December 12--18, 2021 (hybrid meeting) ⋮ Small-ball probabilities for the volume of random convex sets ⋮ Large deviations, moderate deviations, and the KLS conjecture ⋮ Unnamed Item ⋮ Isomorphic properties of intersection bodies ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ Inner and outer approximations of polytopes using boxes. ⋮ (Deterministic) algorithms that compute the volume of polytopes ⋮ Probabilistic Lipschitz analysis of neural networks ⋮ The harmonic polytope ⋮ Dispersion of mass and the complexity of randomized geometric algorithms ⋮ Parallel degree computation for binomial systems ⋮ Learning convex bodies under uniform distribution ⋮ Computing the volume, counting integral points, and exponential sums ⋮ Positive-fraction intersection results and variations of weak epsilon-nets ⋮ A polynomial number of random points does not determine the volume of a convex body ⋮ Approximating the volume of tropical polytopes is difficult ⋮ Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm ⋮ On 0-1 polytopes with many facets ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Active-learning a convex body in low dimensions ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Unnamed Item ⋮ Convex Bodies with Few Faces ⋮ Generating a random collection of discrete joint probability distributions subject to partial information ⋮ Deterministic and randomized polynomial‐time approximation of radii ⋮ A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor ⋮ On the number of polynomials of small house ⋮ Approximate weighted model integration on DNF structures ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Heat flow and a faster algorithm to compute the surface area of a convex body
Cites Work
This page was built for publication: Computing the volume is difficult
