Animation of the minimum-weight matchings of increasingly many points of two colors in a unit square: twitter.com/thienan496/status/

Because the color densities fluctuate, the matching develops regions of many parallel long edges transporting excess density from one place to another. This is reflected mathematically in the fact that the expected length is $$\Theta(\sqrt{n\log n})$$ compared to $$\Theta(\sqrt{n})$$ for non-bipartite matching; see doi.org/10.1007/BF02579135

· · Web · · ·

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!