Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions |
| |
Authors: | P. K. Agarwal B. Aronov M. Sharir |
| |
Affiliation: | (1) Department of Computer Science, Box 90129, Duke University, Durham, NC 27708-0129, USA pankaj@cs.duke.edu , US;(2) Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201, USA aronov@ziggy.poly.edu , US;(3) School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel sharir@math.tau.ac.il and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA, US |
| |
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. Received May 23, 1997, and in revised form October 20, 1997. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|