The union of unit balls has quadratic complexity, even if they all contain the origin
arXiv:cs/9907025
Abstract
We provide a lower bound construction showing that the union of unit balls in three-dimensional space has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.
5 pages, 5 figures