A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets

被引：11

作者：

Toussaint, Godfried T. ^{[1
]}

McAlear, Jim A. ^{[1
]}

机构：

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

来源：

PATTERN RECOGNITION LETTERS | 1982年 / 1卷 / 01期

关键词：

Distance between sets; convex hull; diameter; cluster analysis; algorithms; geometric complexity; pattern recognition;

D O I：

10.1016/0167-8655(82)90046-0

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A simple O(n log n) algorithm is presented for computing the maximum Euclidean distance between two finite planar sets of n points. When the n points form the vertices of simple polygons this complexity reduces to O(n).

引用

页码：21 / 24

页数：4

共 14 条

[1]

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

[2]

Bhattacharya B. K., J ALGORITHM IN PRESS

[3]

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

[4]

ElGindy H., 1981, SOCS8113 MCGILL U

[5]

Graham R. L., 1972, Information Processing Letters, V1, P132, DOI 10.1016/0020-0190(72)90045-2

[6] HIERARCHICAL CLUSTERING SCHEMES [J].

JOHNSON, SC .

PSYCHOMETRIKA, 1967, 32 (03) :241-254

[7]

Lee D. T., 1980, 8011FC04 NW U

[8]

Lee D. T., 1980, 8003FC01 NW U DEP EL

[9] LINEAR ALGORITHM FOR FINDING THE CONVEX-HULL OF A SIMPLE POLYGON [J].

MCCALLUM, D ;

AVIS, D .

INFORMATION PROCESSING LETTERS, 1979, 9 (05) :201-206

[10]

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

← 1 2 →