The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin

Hervé Brönnimann (1) , Olivier Devillers

1 PRISME - Geometry, Algorithms and Robotics

We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.

Mots clés: COMPUTATIONAL GEOMETRY; UNION OF BALLS; GEOMETRIC EXAMPLE

Domaines: Autre [cs.OH]

Hervé Brönnimann, Olivier Devillers. The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin. RR-3758, INRIA. 1999. ⟨inria-00072904⟩