Math @ Duke

Publications [#235419] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, Line transversals of balls and smallest enclosing cylinders in three dimensions,
Discrete & Computational Geometry, vol. 21 no. 3
(1999),
pp. 373388, ISSN 01795376
(last updated on 2018/12/18)
Abstract: We establish a nearcubic 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 nearcubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3space. We also present an approximation algorithm for computing a smallest enclosing cylinder.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

