Line transversals of balls and smallest enclosing cylinders in three dimensions

P. K. Agarwal; B. Aronov; M. Sharir

doi:10.1007/PL00009427

Line transversals of balls and smallest enclosing cylinders in three dimensions

P. K. Agarwal, B. Aronov, M. Sharir

Research output: Contribution to journal › Article › peer-review

Abstract

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder.

Original language	English (US)
Pages (from-to)	373-388
Number of pages	16
Journal	Discrete and Computational Geometry
Volume	21
Issue number	3
DOIs	https://doi.org/10.1007/PL00009427
State	Published - Apr 1999

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/PL00009427

Cite this

@article{96ece6e463a74edc9a009162559394c7,

title = "Line transversals of balls and smallest enclosing cylinders in three dimensions",

abstract = "We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder.",

author = "Agarwal, {P. K.} and B. Aronov and M. Sharir",

year = "1999",

month = apr,

doi = "10.1007/PL00009427",

language = "English (US)",

volume = "21",

pages = "373--388",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Line transversals of balls and smallest enclosing cylinders in three dimensions

AU - Agarwal, P. K.

AU - Aronov, B.

AU - Sharir, M.

PY - 1999/4

Y1 - 1999/4

N2 - We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder.

AB - We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder.

UR - http://www.scopus.com/inward/record.url?scp=0033441871&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033441871&partnerID=8YFLogxK

U2 - 10.1007/PL00009427

DO - 10.1007/PL00009427

M3 - Article

AN - SCOPUS:0033441871

SN - 0179-5376

VL - 21

SP - 373

EP - 388

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

Line transversals of balls and smallest enclosing cylinders in three dimensions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this