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 条

[1] PARTITIONING ARRANGEMENTS OF LINES .2. APPLICATIONS
AGARWAL, PK
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (06) : 533 - 573
[2] PARTITIONING ARRANGEMENTS OF LINES .1. AN EFFICIENT DETERMINISTIC ALGORITHM
AGARWAL, PK
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) : 449 - 483
[3] AGARWAL PK, 1991, 7TH P ACM S COMP GEO, P41
[4] AGARWAL PK, 1992, IN PRESS SIAM J COMP, V21
[5] AGARWAL PK, IN PRESS J ALGORITHM
[6] AGARWAL PK, 1991, UNPUB RANGE SEARCHIN
[7] AGARWAL PK, 1992, 24TH P ACM S THEOR C
[8] ARONOV B, 1991, LECT NOTES COMPUT SC, V519, P13, DOI 10.1007/BFb0028245
[9] BENTLEY J, 1980, J ALGORITHM, V1, P30180
[10] VISIBILITY AND INTERSECTION PROBLEMS IN PLANE GEOMETRY
CHAZELLE, B
GUIBAS, LJ
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) : 551 - 581

← 1 2 3 4 5 →