Abstract
We derive lower bounds on the maximal lengthλ s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form λ2s=1(n)=Ω(nαs(n)), whereα(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower boundλ 3 (n)=Ω(nα(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.Atallah, Dynamic computational geometry,Proc. 24th Symp. on Foundations of Computer Science, (1983), 92–99.
A.Baltsan and M.Sharir, On shortest paths between two convex polyhedra,Tech. Rept. 180, Comp. Science Dept., Courant Institute, Sept. 1985.
H. Davenport andA. Schinzel, A combinatorial problem connected with differential equations,Amer. J. Math.,87 (1965), 684–694.
H. Davenport, A combinatorial problem connected with differential equations, II.Acta Arithmetica,17 (1971), 363–372.
S. Hart andM. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica,6 (1986), 151–177.
D. Leven andM. Sharir, On the number of critical free contacts of a convex polygonal object moving in 2-D polygonal space,Discrete Comput. Geom.,2 (1987), 255–270.
C. O'Dúnlaing, M. Sharir andC. Yap, Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram,Algorithmica,2 (1987), 27–59.
M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences,Combinatorica,7 (1987), 131–143.
E. Szemerédi, On a problem by Davenport and Schinzel,Acta Arithmetica,25 (1974), 213–224.
Author information
Authors and Affiliations
Additional information
Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.