Planar realizations of nonlinear Davenport-Schinzel sequences by segments (Q1098294)

Let \(G=\{\ell_ 1,\ell_ 2,...,\ell_ n\}\) be a collection of n segments in the plane each of which is the graph of a partially defined linear function. Let \(Y_ G\) be the linear function which is the pointwise minimum of the segments \(\ell_ i\). The graph of \(Y_ G\) consists of subsegments of \(\ell_ i\). This paper presents a construction of a set G of n segments for which \(Y_ G\) consists of \(\Omega\) (n \(\alpha\) (n)) subsegments, where \(\alpha\) (n) is the inverse Ackermann function. This kind of construction also gives a tight bound of Davenport-Schinzel sequences of order 3.