Talk:Monge array

Need applications

The thing that's missing here is an explanation of why anyone would care about a Monge array. Dominus 10:27 20 May 2003 (UTC)

I don't have the proof with me, but it has to do with keeping search and sort algorithms, like divide and conquer, within O(nlogn) time. Poor Yorick

I removed this sentence, until such time as someone can explain how it's true. —ajo, 5 Apr 2005

• Monge arrays are useful for keeping growth of functions in O(n log n) time.

I agree, need more applications to motivate why we care about these matrices or what's interesting about them. Evidently if they're widely known in CS, such applications exist. Deco 22:52, 10 August 2006 (UTC)

A Monge matrix M has the nice property that both M and its transpose are Completely Monotone (which needs an entry itself). The row minima or maxima of a completly monotone matrix can be found efficiently $O(n)$ time (rather in $O(n^{2})$ trivially) using an algorithm known as SMAWK . This was used, for example to obtain a sub-quadratic algorithm for string edit distance and for obtaining an efficient algorithm for the single source shortest path problem in planar graphs with negative weights --Algoguy (talk) 17:25, 24 November 2008 (UTC)

References

Matrix or array?

The definition in the article seems to be an abstract definition of a class of matrices, rather than a class of arrays - arrays are only part of the term used and one possible way of storing the matrix. In particular, it's rather difficult to construct arrays of arbitrary real numbers, such as the definition describes, in finite memory. In fact, I think the term is confusing enough that it may be helpful to actually point out some of this in the article itself. What does the author think?

Derrick Coetzee 16:26, 2 May 2004 (UTC)

Well, it's had 9 "authors" already, including you - so I say you should be bold and go ahead. This article could certainly use some actual text explaining things a bit better... - IMSoP 23:42, 17 Jun 2004 (UTC)

Yes, the term "array" is kind of CS-chauvinistic; when I reworked much of the text just now, I changed a lot of "array"s to "matrix"s. But according to Google, a lot of references talk about "Monge arrays," so it's certainly appropriate to use (or at least mention) the terminology that's been established in computer science, rather than (or in addition to) the terminology that's correct from a mathematical standpoint. —ajo, 5 Apr 2005

Linear Combinations?

In mathematics, linear combinations usually include taking negative multiples of the components. So in particular, if monge arrays are really closed under linear combinations, then the negative of any monge array is a monge array. But this is obviously false.