Inflating balls is NP-hard

Guillaume Batog 1 Xavier Goaoc 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2008
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00331423
Contributeur : Xavier Goaoc <>
Soumis le : jeudi 12 novembre 2009 - 19:19:17
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : mardi 9 octobre 2012 - 13:51:02

Fichier

Shadock.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00331423, version 1

Collections

Citation

Guillaume Batog, Xavier Goaoc. Inflating balls is NP-hard. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2008. 〈inria-00331423〉

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

127