Epsilon-covering: a greedy optimal algorithm for simple shapes

Tuong-Bach Nguyen (1) , Isabelle Sivignon (1)

1 GIPSA-AGPIG - GIPSA - Architecture, Géométrie, Perception, Images, Gestes

Unions of balls are widely used shape representations. Given a shape, computing a union of balls that is both accurate in some sense and of small cardinality is thus a challenging problem. In this work, accuracy is ensured by imposing that the union of balls, called covering, is included in the shape and covers a parameterized core set (namely the erosion) of the shape. For a family of simple shapes, we propose a polynomial-time greedy algorithm that computes a covering of minimum cardi-nality for a given shape.

Domaines: Géométrie algorithmique [cs.CG]

Tuong-Bach Nguyen, Isabelle Sivignon. Epsilon-covering: a greedy optimal algorithm for simple shapes. CCCG 2016 - 28th Canadian Conference on Computational Geometry, Aug 2016, Vancouver, Canada. ⟨hal-01400434⟩