The union of unit balls has quadratic complexity, even if they all contain the origin

Simple item page
dc.creatorBronnimann, Herve
dc.creatorDevillers, Olivier
dc.date1999-07-16
dc.date.accessioned2026-07-07T03:24:14Z
dc.date.available2026-07-07T03:24:14Z
dc.descriptionWe 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.
dc.description5 pages, 5 figures
dc.identifierhttps://arxiv.org/abs/cs/9907025
dc.identifierhttp://arxiv.org/abs/cs/9907025
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/33249
dc.subjectComputational Geometry
dc.subjectF.2.2
dc.titleThe union of unit balls has quadratic complexity, even if they all contain the origin
dc.typetext

Files

Collections

arXiv