Inflating balls is NP-hard - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Computational Geometry and Applications Année : 2008

Inflating balls is NP-hard

Résumé

A collection C of balls in R^d is \delta-inflatable if it is isometric to the intersection U \cap E of some d-dimensional affine subspace E with a collection U of (d+\delta)-dimensional balls that are disjoint and have equal radius. We give a quadratic-time algorithm to recognize 1-inflatable collections of balls in any fixed dimension, and show that recognizing \delta-inflatable collections of d-dimensional balls is NP-hard for \delta \geq 2 and d \geq 3 if the balls' centers and radii are given by numbers of the form a+b\sqrt{c+d\sqrt{e}}, where a, ..., e are integers.
Fichier principal
Vignette du fichier
Shadock.pdf (166.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00331423 , version 1 (12-11-2009)

Identifiants

  • HAL Id : inria-00331423 , version 1

Citer

Guillaume Batog, Xavier Goaoc. Inflating balls is NP-hard. International Journal of Computational Geometry and Applications, 2008. ⟨inria-00331423⟩
108 Consultations
205 Téléchargements

Partager

Gmail Facebook X LinkedIn More