Almost linear upper bounds on the length of general Davenport-Schinzel sequences

DOI10.1007/BF02579209zbMath0636.05004OpenAlexW2077909149MaRDI QIDQ1097885

Micha Sharir

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579209

zbMATH Keywords

Davenport-Schinzel sequencesforbidden subsequences

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10)

Related Items (26)

A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\) ⋮ A linear upper bound in extremal theory of sequences ⋮ Generalized Davenport-Schinzel sequences ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram ⋮ Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes ⋮ Planar realizations of nonlinear Davenport-Schinzel sequences by segments ⋮ On the two-dimensional Davenport-Schinzel problem ⋮ Extremal functions for sequences ⋮ Improved lower bounds on the length of Davenport-Schinzel sequences ⋮ A simplified construction of nonlinear Davenport-Schinzel sequences ⋮ A survey of motion planning and related geometric algorithms ⋮ Enumerating Davenport-Schinzel sequences ⋮ Common intersections of polygons ⋮ Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences ⋮ Arrangements of curves in the plane --- topology, combinatorics, and algorithms ⋮ Davenport-Schinzel theory of matrices ⋮ Generalized Davenport-Schinzel sequences with linear upper bound ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts ⋮ Dynamic computational geometry on meshes and hypercubes ⋮ On arrangements of Jordan arcs with three intersections per pair ⋮ An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space ⋮ The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2 ⋮ The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis ⋮ An Output-Sensitive Convex Hull Algorithm for Planar Objects ⋮ Visibility with a moving point of view

Cites Work

• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Efficiency of a Good But Not Linear Set Union Algorithm
• A Combinatorial Problem Connected with Differential Equations
• Some properties of Davenport-Schinzel sequences
• A combinatorial problem connected with differential equations II

This page was built for publication: Almost linear upper bounds on the length of general Davenport-Schinzel sequences