Lie sphere geometry provides a unified representation of points, oriented spheres and hyperplanes in Euclidean d-space as the subset of lines in R𝑑+3 that are contained in a certain quadric. The natural scalar product in this construction is zero if two elements are in oriented contact. We show how the sign of this product can be used to decide if spheres are disjoint. This allows us to model the space of spheres that are not intersecting a given union of spheres as the intersection of half-spaces (and the quadric). The maximal spheres are on the boundary of this set and can be computed by first constructing the intersection of half-spaces, which is a convex hull problem, and then intersecting edges of the hull against the quadric, which are the roots of a univariate quadratic. We demonstrate the method at the example of contouring a discrete signed distance field: every sample of the signed distance field represents an empty spheres and the zero-level contour has to be disjoint from the union of these spheres. Maximal spheres outside the empty spheres provide samples on the zero-level contour. The quality of this sample set is comparable to existing methods relying on optimization, while being deterministic and faster in practice.
Kohlbrenner et al. (Sun,) studied this question.