APPLICATIONS OF A NEW SPACE-PARTITIONING TECHNIQUE

被引：45

作者：

AGARWAL, PK

SHARIR, M

机构：

[1] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL

[2] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1993年 / 9卷 / 01期

关键词：

D O I：

10.1007/BF02189304

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present several applications of a recent space-partitioning technique of Chazelle, Sharir, and Welzl (Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 23-33). Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.

引用

页码：11 / 38

页数：28

共 45 条

[1] PARTITIONING ARRANGEMENTS OF LINES .2. APPLICATIONS [J].