Epsilon-covering is NP-complete
Résumé
Consider the dilation and erosion of a shape S by a ball of radius ε. We call ε-covering of S any collection of balls whose union lies between the dilation and erosion of S. We prove that finding an ε-covering of minimum cardinality is NP-complete, using a reduction from vertex cover.
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...