Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions |
| |
| Authors: | P K Agarwal B Aronov M Sharir |
| |
| Institution: | (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 等数据库收录！ |
|
