Monge array

In computer science, an m-by-n array of real numbers is a Monge array if for all i, j, k, l such that:

$1\leq i<k\leq m$ and $1\leq j<l\leq n$

one obtains:

$A[i,j]+A[k,l]\leq A[i,l]+A[k,j]$

So whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersection points, the sum of the upper-left and lower right elements is less than or equal to the sum of the lower-left and upper-right elements.

This array is a Monge array:

${\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}$

For example, take the intersection of rows 2 and 4 with columns 1 and 5. The four elements are:

${\begin{bmatrix}17&23\\11&7\end{bmatrix}}$

17 + 7 = 24
23 + 11 = 34

It holds that the sum of the upper-left and lower right elements is less than or equal to the sum of the lower-left and upper-right elements.

Monge arrays are useful for keeping growth of functions in O(nlog n) time or less.

See also:

• quasi-convex