(δ,ε)-ball approximation of a shape: definition and complexity

International audienceGiven a set S in Rn, a (δ,ε)-ball approximation of S is defined as a collection of balls that covers the morphological erosion of S (by a ball of radius ε) and remains inside the morphological dilation of S (by a ball of radius δ). We study the problem of computing a (δ,ε)-ball approximation when S is itself defined as a finite union of balls. This problem relates to geometric set cover problems but is however different in nature. It offers a new framework for reducing the size of a collection of balls while controlling both the inner and outer distance to the shape. We prove that computing a (δ,ε)-ball approximation of minimum cardinality is NP-complete for n = 2. Along the way, we study the boundary of unions of disks and their erosion, for which we derive a computational description