Skip to main content
2 of 4
added 173 characters in body
Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651

Monge [1784] described an interesting geometric method to solve this problem. Consider a line that is tangent to both areas, and move the molecule $m$ touched in the first area to the position $x$ touched in the second area, and repeat, until all earth has been transported. Monge's argument that this would be optimum is simple: if molecule $m$ would be moved to another position, then another molecule should be moved to position $x$, implying that the two routes traversed by these molecules cross, and that therefore a shorter assignment exists.

Although geometrically intuitive, the method is however not fully correct, as noted by Appell [1928]: "It is very easy to make the figure in such a way that the routes followed by the two particles of which Monge speaks, do not cross each other."

source: Combinatorial Optimization: Polyhedra and Efficiency, Volume 1, pages 292-293.

See also The strange case of Paul Appell’s last memoir on Monge’s problem: “sur les déblais et remblais”

Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651