Bottleneck Matching in the Plane

05/12/2022

∙

by   Matthew J. Katz, et al.

∙

0

∙

share

We present an algorithm for computing a bottleneck matching in a set of n=2ℓ points in the plane, which runs in O(n^ω/2log n) deterministic time, where ω≈ 2.37 is the exponent of matrix multiplication.