Bottleneck Matching in the Plane

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^{ω/2}\log n)$ deterministic time, where $ω\approx 2.37$ is the exponent of matrix multiplication.

No reviews yet.

No comments yet.