INFLATING BALLS IS NP-HARD

A collection C of balls in R(d) is delta-inflantable if it is isometric to the intersection U boolean AND E of some d-dimensional affine subspace E with a collection U of (d + delta)-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 delta-inflatable collections of 3-dimensional balls is NP-hard for delta >= 2 and d >= 3 if the balls' centers and radii are given by numbers of the from a + b root c + d root e, where a, ... , c are integers.