Line transversals of balls and smallest enclosing cylinders in three dimensions

被引：41

作者：

Agarwal, PK

Aronov, B

Sharir, M

机构：

[1] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

[2] Polytech Univ, Dept Comp & Informat Sci, Brooklyn, NY 11201 USA

[3] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

[4] NYU, Courant Inst Math Sci, New York, NY 10012 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1999年 / 21卷 / 03期

关键词：

D O I：

10.1007/PL00009427

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：373 / 388

页数：16

共 29 条

[21] RAY SHOOTING ON TRIANGLES IN 3-SPACE [J].