Inflating balls is NP-hardReport as inadecuate

Inflating balls is NP-hard - Download this document for free, or read online. Document in PDF available to download.

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.

Author: Guillaume Batog - Xavier Goaoc -



Related documents