Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.(English)Zbl 0697.05003

From the authors’ abstract: “We obtain optimal bounds for the maximal length $$\lambda_ 4(n)$$ of an (n,4) Davenport-Schinzel sequence (a DS(n,4) sequence in short), and then extend them to improve and almost tighten the lower and upper bounds for $$\lambda_ s(n)$$, $$s>4.$$”
Reviewer: P.Reichensperger

MSC:

 05A05 Permutations, words, matrices

Keywords:

Davenport-Schinzel sequence
Full Text:

Online Encyclopedia of Integer Sequences:

Davenport-Schinzel numbers of degree n on 3 symbols.

References:

 [1] Atallah, M; Atallah, M, Dynamic computatinal geometry, (), Comput. math. appl., 11, 1171-1181, (1985) · Zbl 0586.68085 [2] Balstan, A; Sharir, M, On shortest paths between two convex polyhedra, J. ACM, 35, 267-287, (1988) · Zbl 0652.68043 [3] Clarkson, K, Approximate algorithms for shortest path motion planning, (), 56-65 [4] Cole, R; Sharir, M, Visibility problems for polyhedral terrains, J. symbolic computation, 7, 11-30, (1989) [5] Davenport, H; Schinzel, A, A combinatorial problem connected with differential equations, Amer. J. math., 87, 684-689, (1965) · Zbl 0132.00601 [6] Davenport, H, A combinatorial problem connected with differential equations II, Acta arith., 17, 363-372, (1971) · Zbl 0216.30204 [7] {\scH. Edelsbrunner and M. Sharir}, The maximum number of ways to stab n convex non-intersecting objects in the plane is 2n − 2, Tech. Rept. 281, New York University, 1986; Discrete Comput. Geom., to appear. · Zbl 0712.52009 [8] {\scH. Edelsbrunner, L. Guibas, and M. Sharir}, The complexity of many faces in arrangement of lines and of segments, Discrete Comput. Geom., to appear. · Zbl 0691.68035 [9] Guibas, L; Sharir, M; Sifrony, S, On the general motion planning problem with two degrees of freedom, Discrete comput. geom., 4, (1989), in press · Zbl 0685.68049 [10] Hart, S; Sharir, M, Nonlinearity of Davenport-schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177, (1986) · Zbl 0636.05003 [11] {\scK. Kedem and M. Sharir}, An efficient motion planning algorithm for a convex polygonal object in two-dimensional polygonal space, Tech. Rept. 253, Dept. of Computer Science, New York University, 1986; Discrete Comput. Geom., to appear. · Zbl 0688.68039 [12] Leven, D; Sharir, M, On the number of critical free contacts of a convex polygonal objects moving in 2-D polygonal space, Discrete comput. geom., 2, 255-270, (1987) · Zbl 0616.52009 [13] Ó’Dúnlaing, C; Sharir, M; Yap, C, Generalized Voronoi diagrams for a ladder. II. efficient construction of the diagram, Algorithmica, 2, 27-59, (1987) · Zbl 0631.68042 [14] Pach, J; Sharir, M, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates, Discrete comput. geom., 4, (1989) · Zbl 0734.05054 [15] Pollack, R; Sharir, M; Sifrony, S, Separating two simple polygons by a sequence of translations, Discrete comput. geom., 3, 123-136, (1988) · Zbl 0646.68052 [16] Roselle, D.P; Stanton, R.G, Some properties of Davenport-schinzel sequences, Acta arith., 17, 355-362, (1971) · Zbl 0215.33203 [17] {\scJ. Schwartz and M. Sharir}, On the two dimensional Davenport-Schinzel problem, manuscript, 1987; J. Symbolic Computation, to appear. · Zbl 0717.68050 [18] Sharir, M, Almost linear upper bounds on the length of general Davenport-schinzel sequences, Combinatorica, 7, 131-143, (1987) · Zbl 0636.05004 [19] Sharir, M, Improved lower bounds on the length of Davenport-schinzel sequences, Combinatorica, 8, (1988) · Zbl 0672.05015 [20] Szemerédi, E, On a problem by Davenport and schinzel, Acta arith., 25, 213-224, (1974) · Zbl 0291.05003 [21] Wiernik, A; Sharir, M, Planar realizations of nonlinear Davenport-schinzel sequences by segments, Discrete comput. geom., 3, 15-47, (1988) · Zbl 0636.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.