Planar realizations of nonlinear Davenport-Schinzel sequences by segments (Q1098294)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Planar realizations of nonlinear Davenport-Schinzel sequences by segments |
scientific article |
Statements
Planar realizations of nonlinear Davenport-Schinzel sequences by segments (English)
0 references
1988
0 references
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.
0 references
computational geometry
0 references
inverse Ackermann function
0 references
Davenport-Schinzel sequences
0 references
0 references
0 references