Conditional Hardness of Earth Mover Distance

Dhruv Rohatgi

The Earth Mover Distance (EMD) between two sets of points $A,B\subseteq {\mathbb{R}}^d$ with $|A|=|B|$ is the minimum total Euclidean distance of any perfect matching between $A$…