Computing Euclidean bottleneck matchings in higher dimensions

Alon Efrat; Matthew J. Katz

doi:10.1016/S0020-0190(00)00096-X

Computing Euclidean bottleneck matchings in higher dimensions

Alon Efrat
, Matthew J. Katz

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

11 Scopus citations

Abstract

We extend the planar results of Chang et al. (1992) to higher dimensions, and show that given a set A of 2n points in d-space it is possible to compute a Euclidean bottleneck matching of A in roughly O(n^1.5) time, for d≤6, and in subquadratic time, for any constant d>6. If the underlying norm is L_∞, then it is possible to compute a bottleneck matching of A in O(n^1.5 log^0.5 n) time, for any constant d≥2.

Original language	English (US)
Pages (from-to)	169-174
Number of pages	6
Journal	Information Processing Letters
Volume	75
Issue number	4
DOIs	https://doi.org/10.1016/S0020-0190(00)00096-X
State	Published - Sep 30 2000
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/S0020-0190(00)00096-X

Cite this

@article{a9cc3f2c9076481c8ab8fac435ac2e80,

title = "Computing Euclidean bottleneck matchings in higher dimensions",

abstract = "We extend the planar results of Chang et al. (1992) to higher dimensions, and show that given a set A of 2n points in d-space it is possible to compute a Euclidean bottleneck matching of A in roughly O(n1.5) time, for d≤6, and in subquadratic time, for any constant d>6. If the underlying norm is L∞, then it is possible to compute a bottleneck matching of A in O(n1.5 log0.5 n) time, for any constant d≥2.",

author = "Alon Efrat and Katz, \{Matthew J.\}",

year = "2000",

month = sep,

day = "30",

doi = "10.1016/S0020-0190(00)00096-X",

language = "English (US)",

volume = "75",

pages = "169--174",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Computing Euclidean bottleneck matchings in higher dimensions

AU - Efrat, Alon

AU - Katz, Matthew J.

PY - 2000/9/30

Y1 - 2000/9/30

N2 - We extend the planar results of Chang et al. (1992) to higher dimensions, and show that given a set A of 2n points in d-space it is possible to compute a Euclidean bottleneck matching of A in roughly O(n1.5) time, for d≤6, and in subquadratic time, for any constant d>6. If the underlying norm is L∞, then it is possible to compute a bottleneck matching of A in O(n1.5 log0.5 n) time, for any constant d≥2.

AB - We extend the planar results of Chang et al. (1992) to higher dimensions, and show that given a set A of 2n points in d-space it is possible to compute a Euclidean bottleneck matching of A in roughly O(n1.5) time, for d≤6, and in subquadratic time, for any constant d>6. If the underlying norm is L∞, then it is possible to compute a bottleneck matching of A in O(n1.5 log0.5 n) time, for any constant d≥2.

UR - https://www.scopus.com/pages/publications/0034272969

UR - https://www.scopus.com/pages/publications/0034272969#tab=citedBy

U2 - 10.1016/S0020-0190(00)00096-X

DO - 10.1016/S0020-0190(00)00096-X

M3 - Article

AN - SCOPUS:0034272969

SN - 0020-0190

VL - 75

SP - 169

EP - 174

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

Computing Euclidean bottleneck matchings in higher dimensions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this