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 条
[11]   QUASI-OPTIMAL RANGE SEARCHING IN SPACES OF FINITE VC-DIMENSION [J].
CHAZELLE, B ;
WELZL, E .
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 [J].
CLARKSON, KL ;
EDELSBRUNNER, H ;
GUIBAS, LJ ;
SHARIR, M ;
WELZL, E .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :99-160
[18]   VISIBILITY PROBLEMS FOR POLYHEDRAL TERRAINS [J].
COLE, R ;
SHARIR, M .
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
12345