Skip to Main content Skip to Navigation
Reports

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
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072904
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:14:43 AM
Last modification on : Saturday, January 27, 2018 - 1:31:07 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:27:17 PM

Identifiers

  • HAL Id : inria-00072904, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

184

Files downloads

138