2021/04/16 by Marc van Kreveld, van Kreveld, Marc, Frank Staals +7
Computer Science · Social Sciences · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #Historical Geography and Cartography
paper · pdf · doi:10.48550/arxiv.2104.08136
openalex publication_date 2021/04/16 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Given two distributions P and S of equal total mass, the Earth Mover's\nDistance measures the cost of transforming one distribution into the other,\nwhere the cost of moving a unit of mass is equal to the distance over which it\nis moved.\n We give approximation algorithms for the Earth Mover's Distance between\nvarious sets of geometric objects. We give a (1 + \ε)-approximation\nwhen P is a set of weighted points and S is a set of line segments,\ntriangles or d-dimensional simplices. When P and S are both sets of line\nsegments, sets of triangles or sets of simplices, we give a (1 +\n\ε)-approximation with a small additive term. All algorithms run in\ntime polynomial in the size of P and S, and actually calculate the\ntransport plan (that is, a specification of how to move the mass), rather than\njust the cost. To our knowledge, these are the first combinatorial algorithms\nwith a provable approximation ratio for the Earth Mover's Distance when the\nobjects are continuous rather than discrete points.\n