INFLATING BALLS IS NP-HARD
From MaRDI portal
Publication:2893458
DOI10.1142/S0218195911003731zbMath1242.68352OpenAlexW2160617359MaRDI QIDQ2893458
Publication date: 20 June 2012
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195911003731
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial complexity of geometric structures (52C45)
Related Items (1)
Cites Work
- Towards exact geometric computation
- No Helly theorem for stabbing translates by lines in \(\mathbb{R}^3\)
- Upper bounds on geometric permutations for convex sets
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- The different ways of stabbing disjoint convex sets
- Geometric permutations of balls with bounded size disparity.
- A Helly-type theorem for line transversals to disjoint unit balls
- Geometric permutations of disjoint unit spheres
- Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
- Line transversals to disjoint balls
- Helly-type theorems for line transversals to disjoint unit balls
- The maximal number of geometric permutations for \(n\) disjoint translates of a convex set in \(\mathbb R\) is \(\Omega(n)\)
- A Helly-type transversal theorem for \(n\)-dimensional unit balls
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)
This page was built for publication: INFLATING BALLS IS NP-HARD
