Encyclopedia > Monge array

  Article Content

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:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Bugatti

... the automobile company he founded was located in Molsheim[?], in the Alsace region of France. The company was known for its advanced engineering in its premium road cars ...

 
 
 
This page was created in 22.8 ms