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

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Computational Geometry, F.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/33249

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/9907025
 http://arxiv.org/abs/cs/9907025

Collections

arXiv