INFLATING BALLS IS NP-HARD
Guillaume Batog, Xavier Goaoc · International Journal of Computational Geometry & Applications · 2011
A collection [Formula: see text] of balls in ℝd is δ-inflatable if it is isometric to the intersection [Formula: see text] of some d-dimensional affine subspace E with a collection [Formula: see text] of (d + δ)-dimensional balls that are disjoint and have equal radius. We give a quadratic-time algorithm to recognize 1-inflatable collections of balls in any fixed dimension, and show that recognizing δ-inflatable collections of d-dimensional balls is NP-hard for δ ≥ 2 and d ≥ 3 if the balls' centers and radii are given by numbers of the form [Formula: see text] where a, …, e are integers.