Inflating balls is NP-hard

DOI10.1142/S0218195911003731MaRDI QIDQ2893458zbMATHOpenAlexFDO

Authors Guillaume Batog, Xavier Goaoc

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

zbMATH Keywords

inflationgeometric transversaldisjoint unit ball

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Recommendations

• Hitting or avoiding balls in Euclidean space
• The problem of a minimal ball enclosing k points
• \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity
• Optimization approach for solving some geometry problems
• Geometric algorithms for finding a point in the intersection of balls

Cites work

• A Helly-type theorem for line transversals to disjoint unit balls
• A Helly-type transversal theorem for \(n\)-dimensional unit balls
• A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)
• Geometric permutations of balls with bounded size disparity.
• Geometric permutations of disjoint unit spheres
• Helly-type theorems for line transversals to disjoint unit balls
• Line transversals to disjoint balls
• No Helly theorem for stabbing translates by lines in \(\mathbb{R}^3\)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
• The different ways of stabbing disjoint convex sets
• The maximal number of geometric permutations for \(n\) disjoint translates of a convex set in \(\mathbb R\) is \(\Omega(n)\)
• The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
• Towards exact geometric computation
• Upper bounds on geometric permutations for convex sets

Cited in

(1)

• Helly-type theorems for line transversals to disjoint unit balls

This page was built for publication: Inflating balls is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2893458)