(δ,ε)-ball approximation of a shape: definition and complexity - AGPIG Accéder directement au contenu
Article Dans Une Revue Discrete and Computational Geometry Année : 2019

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

Résumé

Given 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.
Fichier principal
Vignette du fichier
final.pdf (737.12 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01798844 , version 1 (24-05-2018)

Identifiants

Citer

Dominique Attali, Tuong-Bach Nguyen, Isabelle Sivignon. (δ,ε)-ball approximation of a shape: definition and complexity. Discrete and Computational Geometry, 2019, 61 (3), pp.595-625. ⟨10.1007/s00454-018-0019-8⟩. ⟨hal-01798844⟩
122 Consultations
252 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More