page_title: Davenport–Schinzel sequence
section_title: Application to lower envelopes
hierarchical_section_title: Davenport–Schinzel sequence / Application to lower envelopes
context_page_description: In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are allowed. Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations. Following Atallah these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.
context_section_description: The lower envelope of a set of functions ƒᵢ(x) of a real variable x is the function given by their pointwise minimum:
  ƒ(x) = minᵢƒᵢ(x).
  Suppose that these functions are particularly well behaved: they are all continuous, and any two of them are equal on at most s values. With these assumptions, the real line can be partitioned into finitely many intervals within which one function has values smaller than all of the other functions. The sequence of these intervals, labeled by the minimizing function within each interval, forms a Davenport–Schinzel sequence of order s. Thus, any upper bound on the complexity of a Davenport–Schinzel sequence of this order also bounds the number of intervals in this representation of the lower envelope.
  In the original application of Davenport and Schinzel, the functions under consideration were a set of different solutions to the same homogeneous linear differential equation of order s. Any two distinct solutions can have at most s values in common, so the lower envelope of a set of n distinct solutions forms a DS(n,s)-sequence.
  The same concept of a lower envelope can also be applied to functions that are only piecewise continuous or that are defined only over intervals of the real line; however, in this case, the points of discontinuity of the functions and the endpoints of the interval within which each function is defined add to the order of the sequence. 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.
caption: A Davenport–Schinzel sequence of order 3 formed by the lower envelope of line segments.