Skip to main content
4 of 4
deleted 192 characters in body
Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651

Schrijver explains Monge's reasoning in On the history of combinatorial optimization (till 1960):

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."

Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651