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:
- and
one obtains:
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:
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: