Heng Cao, Haifeng Xi, et al.
WSC 2003
The 1935 result of Erdos and Szekeres that any sequence of ≥ n 2 + 1 real numbers contains a monotonic subsequence of ≥ n + 1 terms has stimulated extensive further research, including a paper of J. B. Kruskal that defined an extension of monotonicity for higher dimensions. This paper provides a proof of a weakened form of Kruskal's conjecture for 2-dimensional Euclidean space by showing that there exist sequences of n points in the plane for which the longest monotonic subsequences have length ≤ n1/2 + 3. Weaker results are obtained for higher dimensions. When points are selected at random from reasonable distributions, the average length of the longest monotonic subsequence is shown to be ∼2n1/2 as n → ∞ for each dimension.
Heng Cao, Haifeng Xi, et al.
WSC 2003
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
L Auslander, E Feig, et al.
Advances in Applied Mathematics
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990