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:

<math> 1 \le i < k \le m </math> and <math> 1 \le j < l \le n </math>

which yields:

<math>A[i,j] + A[k,l] \le A[i,l] + A[k,j] </math>

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:

<math>

\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}</math>

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

<Math>

\begin{bmatrix} 17 & 23\\ 11 & 7 \end{bmatrix}</math>

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(nlogn) time or less.

See also:

• quasi-convex[?]