Math @ Duke

Publications [#235590] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, Line transversals of balls and smallest enclosing cylinders in three dimensions,
in Eighth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1997),
pp. 483492
(last updated on 2017/12/13)
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

