Inflating balls is NP-hardReportar como inadecuado

Inflating balls is NP-hard - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Guillaume Batog - Xavier Goaoc -



Documentos relacionados