COMPUTING SOME DISTANCE FUNCTIONS BETWEEN POLYGONS

被引：15

作者：

ATALLAH, MJ ^{[1
]}

RIBEIRO, CC ^{[1
]}

LIFSCHITZ, S ^{[1
]}

机构：

[1] UNIV RIO JANEIRO,DEPT ELECT ENGN,CAIXA POSTAL 38063,GAVEA 22452,RJ,BRAZIL

来源：

PATTERN RECOGNITION | 1991年 / 24卷 / 08期

基金：

美国国家科学基金会;

关键词：

COMPUTATIONAL GEOMETRY; POLYGONS; DISTANCE COMPUTATION; HAUSDORFF DISTANCE; PATTERN RECOGNITION; CONTOUR FITTING; ROBOT VISION; ALGORITHMS;

D O I：

10.1016/0031-3203(91)90045-7

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We present algorithms for computing some distance functions between two (possibly intersecting) polygons, in both the convex and nonconvex cases. The interest for such distance functions comes from applications in robot vision, pattern recognition and contour fitting. We present an optimal EREW-PRAM parallel algorithm for the case when the input polygons are convex, and an essentially quadratic sequential algorithm for the case of arbitrary polygons (possibly with holes).

引用

页码：775 / 781

页数：7

共 18 条

[1] A LINEAR TIME ALGORITHM FOR THE HAUSDORFF DISTANCE BETWEEN CONVEX POLYGONS [J].

ATALLAH, MJ .

INFORMATION PROCESSING LETTERS, 1983, 17 (04) :207-209

[2] ADAPTIVE BITONIC SORTING - AN OPTIMAL PARALLEL ALGORITHM FOR SHARED-MEMORY MACHINES [J].

BILARDI, G ;

NICOLAU, A .

SIAM JOURNAL ON COMPUTING, 1989, 18 (02) :216-228

[3] PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].

BRENT, RP .

JOURNAL OF THE ACM, 1974, 21 (02) :201-206

[4]

CHAZELLE B, 1989, 30TH P ANN IEEE S F, P586

[5]

CHEN DZ, 1989, TR89928 PURD U DEP C

[6] OPTIMAL MATCHING OF CONVEX POLYGONS [J].

COX, P ;

MAITRE, H ;

MINOUX, M ;

RIBEIRO, C .

PATTERN RECOGNITION LETTERS, 1989, 9 (05) :327-334

[7] FAST DETECTION OF POLYHEDRAL INTERSECTION [J].

DOBKIN, DP ;

KIRKPATRICK, DG .

THEORETICAL COMPUTER SCIENCE, 1983, 27 (03) :241-253

[8] A LINEAR ALGORITHM FOR DETERMINING THE SEPARATION OF CONVEX POLYHEDRA [J].

DOBKIN, DP ;

KIRKPATRICK, DG .

JOURNAL OF ALGORITHMS, 1985, 6 (03) :381-392

[9] TRIANGULATING A SIMPLE POLYGON [J].

GAREY, MR ;

JOHNSON, DS ;

PREPARATA, FP ;

TARJAN, RE .

INFORMATION PROCESSING LETTERS, 1978, 7 (04) :175-179

[10]

Grunbaum B., 2003, CONVEX POLYTOPES, V2nd

← 1 2 →