Planar realizations of nonlinear Davenport-Schinzel sequences by segments. (English) Zbl 0636.68043

Let \(G=\{\ell_ 1,\ell_ 2,...,\ell_ n\}\) be a collection of n segments in the plane each of which is the graph of a partially defined linear function. Let \(Y_ G\) be the linear function which is the pointwise minimum of the segments \(\ell_ i\). The graph of \(Y_ G\) consists of subsegments of \(\ell_ i\). This paper presents a construction of a set G of n segments for which \(Y_ G\) consists of \(\Omega\) (n \(\alpha\) (n)) subsegments, where \(\alpha\) (n) is the inverse Ackermann function. This kind of construction also gives a tight bound of Davenport-Schinzel sequences of order 3.
Reviewer: K.W.Lih


68Q25 Analysis of algorithms and problem complexity
05A05 Permutations, words, matrices
68R99 Discrete mathematics in relation to computer science
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
Full Text: DOI EuDML


[1] W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen,Math. Ann99 (1928), 118-133. · Zbl 0087.19001 · doi:10.1007/BF01459088
[2] M. Atallah, Dynamic computational geometry,Proceedings of the 24th Symposium on Foundations of Computer Science, 92-99, 1983. (Also inComput. Math. Appl.11 (1985), 1171-1181.) · Zbl 0586.68085
[3] A. Baltsan and M. Sharir, On Shortest Paths Between Two Convex Polyhedra, Technical Report No. 180, Computer Science Department, New York University, 1985. (To appear inJ. Assoc. Comput. Mach.) · Zbl 0652.68043
[4] R. Cole and M. Sharir, Visibility of a Polyhedral Surface from a Point, Technical Report No. 266, Computer Science Department, New York University, 1986. (To appear inJ. Symbolic Comput.)
[5] H. Davenport, A combinatorial problem connected with differential equations, II,Acta Arith.17 (1971), 363-372. · Zbl 0216.30204
[6] H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations,Amer. J. Math.87 (1965), 684-694. · Zbl 0132.00601 · doi:10.2307/2373068
[7] S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica6 (1986), 151-177. · Zbl 0636.05003 · doi:10.1007/BF02579170
[8] P. Komjath, private communication.
[9] D. Leven and M. Sharir, On the Number of Critical Free Contacts of a Convex Polygonal Object Moving in Two-Dimensional Polygonal Space, Technical Report No. 187, Computer Science Department, New York University, 1985. (Also inDiscrete Comput. Geom.2 (1987), 255-270.) · Zbl 0616.52009
[10] C. Ó’Dúnlaing, M. Sharir, and C. K. Yap, Generalized Voronoi diagrams for a ladder, II: Efficient construction of the diagram,Algorithmica2 (1987), 27-59. · Zbl 0631.68042 · doi:10.1007/BF01840348
[11] R. Pollack, M. Sharir, and S. Sifrony, Separating Two Simple Polygons by a Sequence of Translations, Technical Report No. 215, Computer Science Department, New York University, 1986. (To appear inDiscrete Comput. Geom.). · Zbl 0646.68052
[12] D. P. Roselle and R. G. Stanton, Some properties of Davenport-Schinzel sequences,Acta Arith.17 (1971), 355-362. · Zbl 0424.68036
[13] M. Sharir, Almost Linear Upper Bounds on the Length of General Davenport-Schinzel Sequences,Combinatorica7 (1987), 131-143. · Zbl 0636.05004 · doi:10.1007/BF02579209
[14] M. Sharir, Improved Lower Bound on the Length of Davenport-Schinzel Sequences, Technical Report No. 204, Computer Science Department, New York University, 1986. (To appear inCombinatorica.) · Zbl 0672.05015
[15] E. Szemeredi, On a problem of Davenport and Schinzel,Acta Arith.25 (1974), 213-224. · Zbl 0291.05003
[16] J. Pach and M. Sharir, The Upper Envelope of Piecewise Linear Functions and the Boundary of a Region Enclosed by Convex Plates: Combinatorial Analysis, Technical Report No. 279, Computer Science Department, New York University, 1987. · Zbl 0734.05054
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.