Characterization of line width variation
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
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.
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
Chai Wah Wu
Linear Algebra and Its Applications
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems