Davenport–Schinzel sequence

Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations.

Following Atallah (1985) these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.

Due to the very rapid growth of the Ackermann function, its inverse α grows very slowly, and is at most four for problems of any practical size.

[3] Using big O and big Θ notation, the following bounds are known: The value of λs(n) is also known when s is variable but n is a small constant:[10] When s is a function of n the upper and lower bounds on Davenport-Schinzel sequences are not tight.

For instance, a non-vertical line segment in the plane can be interpreted as the graph of a function mapping an interval of x values to their corresponding y values, and the lower envelope of a collection of line segments forms a Davenport–Schinzel sequence of order three because any two line segments can form an alternating subsequence with length at most four.