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

Godfried T. Toussaint; Jim A. McAlear

doi:10.1016/0167-8655(82)90046-0

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

Godfried T. Toussaint, Jim A. McAlear

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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).

Original language	English (US)
Pages (from-to)	21-24
Number of pages	4
Journal	Pattern Recognition Letters
Volume	1
Issue number	1
DOIs	https://doi.org/10.1016/0167-8655(82)90046-0
State	Published - Oct 1982

Keywords

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

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0167-8655(82)90046-0

Cite this

@article{0173ba5735f64de7993d0446f9c063c6,

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

abstract = "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).",

keywords = "Distance between sets, algorithms, cluster analysis, convex hull, diameter, geometric complexity, pattern recognition",

author = "Toussaint, {Godfried T.} and McAlear, {Jim A.}",

year = "1982",

month = oct,

doi = "10.1016/0167-8655(82)90046-0",

language = "English (US)",

volume = "1",

pages = "21--24",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

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

AU - Toussaint, Godfried T.

AU - McAlear, Jim A.

PY - 1982/10

Y1 - 1982/10

N2 - 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).

AB - 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).

KW - Distance between sets

KW - algorithms

KW - cluster analysis

KW - convex hull

KW - diameter

KW - geometric complexity

KW - pattern recognition

UR - http://www.scopus.com/inward/record.url?scp=0020375306&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020375306&partnerID=8YFLogxK

U2 - 10.1016/0167-8655(82)90046-0

DO - 10.1016/0167-8655(82)90046-0

M3 - Article

AN - SCOPUS:0020375306

SN - 0167-8655

VL - 1

SP - 21

EP - 24

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this