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

Godfried T. Toussaint; Binay K. Bhattacharya

doi:10.1016/0167-8655(83)90041-7

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

Godfried T. Toussaint, Binay K. Bhattacharya

Computer Science

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

Abstract

It is shown in this paper that the minimum distance between two finite planar sets of n points can be computer 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 O(n).

Original language	English (US)
Pages (from-to)	79-82
Number of pages	4
Journal	Pattern Recognition Letters
Volume	2
Issue number	2
DOIs	https://doi.org/10.1016/0167-8655(83)90041-7
State	Published - Dec 1983

Keywords

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

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0167-8655(83)90041-7

Cite this

@article{e44606ee6a3344408c255bda6736230e,

title = "Optimal algorithms for computing the minimum distance between two finite planar sets",

abstract = "It is shown in this paper that the minimum distance between two finite planar sets of n points can be computer 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 O(n).",

keywords = "Minimum distance between sets, algorithms, cluster analysis, coloring problems, complexity, computational geometry, convex polygons, pattern recognition",

author = "Toussaint, {Godfried T.} and Bhattacharya, {Binay K.}",

year = "1983",

month = dec,

doi = "10.1016/0167-8655(83)90041-7",

language = "English (US)",

volume = "2",

pages = "79--82",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

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

AU - Toussaint, Godfried T.

AU - Bhattacharya, Binay K.

PY - 1983/12

Y1 - 1983/12

N2 - It is shown in this paper that the minimum distance between two finite planar sets of n points can be computer 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 O(n).

AB - It is shown in this paper that the minimum distance between two finite planar sets of n points can be computer 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 O(n).

KW - Minimum distance between sets

KW - algorithms

KW - cluster analysis

KW - coloring problems

KW - complexity

KW - computational geometry

KW - convex polygons

KW - pattern recognition

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

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

U2 - 10.1016/0167-8655(83)90041-7

DO - 10.1016/0167-8655(83)90041-7

M3 - Article

AN - SCOPUS:0021058680

SN - 0167-8655

VL - 2

SP - 79

EP - 82

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this