Article ID: | iaor19971780 |
Country: | Netherlands |
Volume: | 69 |
Issue: | 1 |
Start Page Number: | 47 |
End Page Number: | 64 |
Publication Date: | Jan 1997 |
Journal: | Annals of Operations Research |
Authors: | Ibaraki Toshihide, Crama Yves |
Keywords: | combinatorial analysis |
The authors investigate the algorithmic complexity of several geometric problems of the following type: given a ‘feasible’ box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. They establish that all these problems are NP-hard in their most general version. The authors derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, they show that all these problems can be solved in polynomial time when the dimension of the space is fixed.