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