No label defined (Q4945501)

The authors survey the basic results on the Davenport-Schinzel sequences (DS-sequences) and discuss their applications to a variety of geometric problems. It is pointed out that DS-sequences provide very valuable tools in the analysis of combinatorial and algorithmic problems in geometry, and play a very important role in geometric problems involving arrangements of curves and surfaces. A sequence \(U= \{u_1,u_2,\dots, u_m\}\) of integers is an \((n,s)\) DS-sequence (\(n\), \(s\) being positive integers) if it satisfies the following conditions: (i) \(1\leq u_i\leq n\) for each \(i\leq m\), (ii) \(u_i\neq u_{i+1}\) for each \(i< m\), and (iii) there do not exist \(s+2\) indices \(1\leq i_1< i_2<\cdots< i_{s+2}\leq m\) such that \(u_{i_1}= u_{i_3}= u_{i_5}=\cdots= a\), \(u_{i_2}, u_{i_4}=\cdots= b\), where \(a\neq b\). The length of the sequence \(u\) is defined to be \(|U|= m\), \(s\) is called the order of \(U\), and \(m\) the number of symbols composing \(U\). The topics surveyed deal with showing the connection between DS-sequences and lower envelopes, discussing the analysis of the maximum length of \((n,s)\) DS-sequences, and presenting basic combinatorial geometric applications of DS-sequences to two-dimensional arrangements of lines, segments, and arcs. For the entire collection see [Zbl 0930.65001].