APPLICATIONS OF A NEW SPACE-PARTITIONING TECHNIQUE

被引：44

作者：

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 条

[11] QUASI-OPTIMAL RANGE SEARCHING IN SPACES OF FINITE VC-DIMENSION
CHAZELLE, B
WELZL, E
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) : 467 - 489
[12] CHAZELLE B, 1991, 32 ANN IEEE S FDN CO, P29
[13] CHAZELLE B, 1990, 491 NEW YORK U DEP C
[14] CHAZELLE B, 1991, 18TH P INT C AUT LAN, P661
[15] CHENG SW, 1991, 2ND P ANN ACM SIAM S, P7
[16] CHENG SW, 1990, 31ST P IEEE S F COMP, P96
[17] COMBINATORIAL COMPLEXITY-BOUNDS FOR ARRANGEMENTS OF CURVES AND SPHERES
CLARKSON, KL
EDELSBRUNNER, H
GUIBAS, LJ
SHARIR, M
WELZL, E
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) : 99 - 160
[18] VISIBILITY PROBLEMS FOR POLYHEDRAL TERRAINS
COLE, R
SHARIR, M
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1989, 7 (01) : 11 - 30
[19] DEBERG M, 1991, 7TH P S COMP GEOM, P21
[20] DOBKIN D, 1990, 17TH P INT C AUT LAN, P400

← 1 2 3 4 5 →