Bottleneck Matching in the Plane

Abstract

We present an algorithm for computing a bottleneck matching in a set of $n=2\ell$ points in the plane, which runs in $O(n^{\omega /2}\log n)$ deterministic time, where $\omega \approx 2.37$ is the exponent of matrix multiplication.