COMPUTING THE INTERSECTION-DEPTH OF POLYHEDRA

被引：98

作者：

DOBKIN, D

HERSHBERGER, J

KIRKPATRICK, D

SURI, S

机构：

[1] BELL COMMUN RES INC,MORRISTOWN,NJ 07960

[2] DEC SYST RES CTR,PALO ALTO,CA 94301

[3] UNIV BRITISH COLUMBIA,DEPT COMP SCI,VANCOUVER V6T 1W5,BC,CANADA

来源：

ALGORITHMICA | 1993年 / 9卷 / 06期

关键词：

INTERSECTION; MINKOWSKI SUM; PLANE SWEEP; RAY SHOOTING; POLYHEDRAL HIERARCHY;

D O I：

10.1007/BF01190153

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given two intersecting polyhedra P, Q and a direction d, find the smallest translation of Q along d that renders the interiors of P and Q disjoint. The same problem can also be posed without specifying the direction, in which case the minimum translation over all directions is sought. These are fundamental problems that arise in robotics and computer vision. We develop techniques for implicitly building and searching convolutions and apply them to derive efficient algorithms for these problems.

引用

页码：518 / 533

页数：16

共 30 条

[1] A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON [J].

AGGARWAL, A ;

GUIBAS, LJ ;

SAXE, J ;

SHOR, PW .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :591-604

[2]

Asano T., 1985, Transactions of the Institute of Electronics and Communication Engineers of Japan, Section E (English), VE68, P557

[3]

BAKER BS, 1986, J ALGORITHM, P532

[4]

BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432

[5]

CAMERON SA, 1986, IEEE T ROBOTIC AUTOM, P591

[6] INTERSECTION OF CONVEX OBJECTS IN 2-DIMENSION AND 3-DIMENSION [J].

CHAZELLE, B ;

DOBKIN, DP .

JOURNAL OF THE ACM, 1987, 34 (01) :1-27

[7]

CHAZELLE B, 1990, 31ST P ANN IEEE S F, P220

[8]

CHIN F, 1983, IEEE T COMPUT, V32, P1203, DOI 10.1109/TC.1983.1676186

[9]

DOBKIN DP, 1982, LECT NOTES COMPUT SC, V140, P154

[10]

DOBKIN DP, 1990, LECT NOTES COMPUT SC, V443, P400, DOI 10.1007/BFb0032047

← 1 2 3 →