2023/06/21 by William Q. Erickson, Erickson, William Q.
Computer Science · Engineering · Mathematics · #52B05 (Primary) 62R01 (Secondary) #Combinatorics (math.CO) #Control and Dynamics of Mobile Robots #FOS: Mathematics #Graph Labeling and Dimension Problems #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.2306.12030
openalex publication_date 2023/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The earth mover's distance (EMD) is a well-known metric on spaces of histograms; roughly speaking, the EMD measures the minimum amount of work required to equalize two histograms. The EMD has a natural generalization that compares an arbitrary number of histograms; in this case, the EMD can be viewed as hypervolume in d dimensions, where the histograms are vertices of a d-simplex. For d=2, it is known that the EMD between three histograms equals half the sum of the pairwise EMDs -- a sort of Heron's formula for histograms, but where the area equals the semiperimeter. In this paper, by introducing an object we call the earth mover's simplex, we prove two generalizations of this Heron-like formula in arbitrary dimension: the first (a sort of Cayley-Menger formula) expresses the EMD in terms of the edge lengths (the pairwise EMDs), the second in terms of the facets (EMDs excluding one histogram).