Optimal algorithms for computing the minimum distance between two finite planar sets

被引：17

作者：

Toussaint, Godfried T. ^{[1
]}

Bhattacharya, Binay K. ^{[2
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ H3A 2K6, Canada

[2] Simon Fraser Univ, Dept Comp Sci, Burnaby, BC V5A 1S6, Canada

来源：

PATTERN RECOGNITION LETTERS | 1983年 / 2卷 / 02期

关键词：

Minimum distance between sets; cluster analysis; pattern recognition; coloring problems; convex polygons; algorithms; computational geometry; complexity;

D O I：

10.1016/0167-8655(83)90041-7

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

It is shown in this paper that the minimum distance between two finite planar sets of n points can be computed in O(n log n) worst-case running time and that this is optimal to within a constant factor. Furthermore, when the sets form a convex polygon this complexity can be reduced to O(n).

引用

页码：79 / 82

页数：4

共 14 条

[1]

Avis D., 1980, P ALL C URB IL OCT 1

[2]

Duda R.O., 1973, PATTERN CLASSIFICATI, P235

[3]

Horspool R.N., 1979, SOCS7912 MCGILL U

[4] ALL NEAREST-NEIGHBOR PROBLEM FOR CONVEX POLYGONS [J].

LEE, DT ;

PREPARATA, FP .

INFORMATION PROCESSING LETTERS, 1978, 7 (04) :189-192

[5] 2 ALGORITHMS FOR CONSTRUCTING A DELAUNAY TRIANGULATION [J].

LEE, DT ;

SCHACHTER, BJ .

INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES, 1980, 9 (03) :219-242

[6]

MATULA DW, 1980, GEOGR ANAL, V12, P205

[7]

McKenna M., 1983, SOCS836 MCGILL U

[8]

Shamos M. I., 1975, P 7 ANN ACM S THEORY, P224

[9]

Shamos Michael I., 1978, THESIS YALE U

[10]

Supowit K.J., 1983, JACM IN PRESS

← 1 2 →