AN OPTIMAL ALGORITHM FOR INTERSECTING 3-DIMENSIONAL CONVEX POLYHEDRA

被引：51

作者：

CHAZELLE, B

机构：

[1] Princeton Univ, Princeton, NJ

来源：

SIAM JOURNAL ON COMPUTING | 1992年 / 21卷 / 04期

关键词：

COMPUTATIONAL GEOMETRY; CONVEX POLYHEDRA;

D O I：

10.1137/0221041

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper describes a linear-time algorithm for computing the intersection of two convex polyhedra in 3-space. Applications of this result to computing intersections, convex hulls, and Voronoi diagrams are also given.

引用

页码：671 / 696

页数：26

共 26 条

[1] AGGARWAL A, 1987, 19TH P ACM S THEOR C, P39
[2] [Anonymous], 1987, EATCS MONOGRAPHS THE
[3] Baumgart BG, 1975, AFIPS P, P589, DOI DOI 10.1145/1499949.1500071
[4] DIVIDE AND CONQUER FOR LINEAR EXPECTED TIME
BENTLEY, JL
SHAMOS, MI
[J]. INFORMATION PROCESSING LETTERS, 1978, 7 (02) : 87 - 91
[5] INTERSECTION OF CONVEX OBJECTS IN 2-DIMENSION AND 3-DIMENSION
CHAZELLE, B
DOBKIN, DP
[J]. JOURNAL OF THE ACM, 1987, 34 (01) : 1 - 27
[6] FAST DETECTION OF POLYHEDRAL INTERSECTION
DOBKIN, DP
KIRKPATRICK, DG
[J]. THEORETICAL COMPUTER SCIENCE, 1983, 27 (03) : 241 - 253
[7] A LINEAR ALGORITHM FOR DETERMINING THE SEPARATION OF CONVEX POLYHEDRA
DOBKIN, DP
KIRKPATRICK, DG
[J]. JOURNAL OF ALGORITHMS, 1985, 6 (03) : 381 - 392
[8] EFFICIENT USES OF THE PAST
DOBKIN, DP
MUNRO, JI
[J]. JOURNAL OF ALGORITHMS, 1985, 6 (04) : 455 - 465
[9] DOBKIN DP, 1987, 3RD P ACM S COMP GEO, P86
[10] LINEAR TIME ALGORITHMS FOR 2-VARIABLE AND 3-VARIABLE LINEAR-PROGRAMS
DYER, ME
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (01) : 31 - 45

← 1 2 3 →