  One of the longest-standing open problems in computational geometry is to
bound the lower envelope of $n$ univariate functions, each pair of which
crosses at most $s$ times, for some fixed $s$. This problem is known to be
equivalent to bounding the length of an order-$s$ Davenport-Schinzel sequence,
namely a sequence over an $n$-letter alphabet that avoids alternating
subsequences of the form $a \cdots b \cdots a \cdots b \cdots$ with length
$s+2$. These sequences were introduced by Davenport and Schinzel in 1965 to
model a certain problem in differential equations and have since been applied
to bounding the running times of geometric algorithms, data structures, and the
combinatorial complexity of geometric arrangements.
  Let $\lambda_s(n)$ be the maximum length of an order-$s$ DS sequence over $n$
letters. What is $\lambda_s$ asymptotically? This question has been answered
satisfactorily (by Hart and Sharir, Agarwal, Sharir, and Shor, Klazar, and
Nivasch) when $s$ is even or $s\le 3$. However, since the work of Agarwal,
Sharir, and Shor in the mid-1980s there has been a persistent gap in our
understanding of the odd orders.
  In this work we effectively close the problem by establishing sharp bounds on
Davenport-Schinzel sequences of every order $s$. Our results reveal that,
contrary to one's intuition, $\lambda_s(n)$ behaves essentially like
$\lambda_{s-1}(n)$ when $s$ is odd. This refutes conjectures due to Alon et al.
(2008) and Nivasch (2010).
