6.5.2 Davenport-Schinzel Sequences

Davenport-Schinzel sequences provide a powerful characterization of the structure that arises from the lower or upper envelope of a collection of functions. The lower envelope of five functions is depicted in Figure 6.42. Such envelopes arise in many problems throughout computational geometry, including many motion planning problems. They are an important part of the design and analysis of many modern algorithms, and the resulting algorithm's time complexity usually involves terms that follow directly from the sequences. Therefore, it is worthwhile to understand some of the basics before interpreting some of the results of Section 6.5.3. Much more information on Davenport-Schinzel sequences and their applications appears in [866]. The brief introduction presented here is based on [865].

Figure 6.42: The lower envelope of a collection of functions.

For positive integers $n$ and $s$, an $(n,s)$ Davenport-Schinzel sequence is a sequence $(u_1,\ldots,u_m)$ composed from a set of $n$ symbols such that:

1. The same symbol may not appear consecutively in the sequence. In other words, $u_i \not = u_{i+1}$ for any $i$ such that $1 \leq i < m$.
2. The sequence does not contain any alternating subsequence that uses two symbols and has length $s+2$. A subsequence can be formed by deleting any elements in the original sequence. The condition can be expressed as: There do not exist $s+2$ indices $i_1 < i_2 < \cdots < i_{s+2}$ for which $u_{i_1} = u_{i_3} = u_{i_5} = a$ and $u_{i_2} = u_{i_4} = u_{i_6} = b$, for some symbols $a$ and $b$.

As an example, an $(n,3)$ sequence cannot appear as $(a \cdots b \cdots a \cdots b \cdots a)$, in which each $\cdots$ is filled in with any sequence of symbols. Let $\lambda_s(n)$ denote the maximum possible length of an $(n,s)$ Davenport-Schinzel sequence.

The connection between Figure 6.42 and these sequences can now be explained. Consider the sequence of function indices that visit the lower envelope. In the example, this sequence is $(5,2,3,4,1)$. Suppose it is known that each pair of functions intersects in at most $s$ places. If there are $n$ real-valued continuous functions, then the sequence of function indices must be an $(n,s)$ Davenport-Schinzel sequence. It is amazing that such sequences cannot be very long. For a fixed $s$, they are close to being linear.

The standard bounds for Davenport-Schinzel sequences are [865]^6.9

$$\lambda_1(n) = n$$ (6.32)

$$\lambda_2(n) = 2 n - 1$$ (6.33)

$$\lambda_3(n) = \Theta(n \alpha(n))$$ (6.34)

$$\lambda_4(n) = \Theta(n \cdot 2^{\alpha(n)})$$ (6.35)

$$\lambda_{2s}(n) \leq n \cdot 2^{\alpha(n)^{s-1}+C_{2s}(n)}$$ (6.36)

$$\lambda_{2s+1}(n) \leq n \cdot 2^{\alpha(n)^{s-1}\lg\alpha(n)+C^\prime_{2s+1}(n)}$$ (6.37)

$$\lambda_{2s}(n) = \Omega(n \cdot 2^{\frac{1}{(s-1)!} \alpha(n)^{s-1}+C^\prime_{2s}(n)}) .$$ (6.38)

In the expressions above $C_r(n)$ and $C^\prime_r(n)$ are terms that are smaller than their leading exponents. The $\alpha(n)$ term is the inverse Ackerman function, which is an extremely slow-growing function that appears frequently in algorithms. The Ackerman function is defined as follows. Let $A_1(m) = 2m$ and $A_{n+1}(m)$ represent $m$ applications of $A_n$. Thus, $A_1(m)$ performs doubling, $A_2(m)$ performs exponentiation, and $A_3(m)$ performs tower exponentiation, which makes a stack of $2$'s,

$$2^{2^{\mathinner{ \mkern1mu\raise1pt\hbox{.} \mkern2mu\raise4pt\hbox{.} \mkern2mu\raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu}^{2^2}}},$$ (6.39)

that has height $m$. The Ackerman function is defined as $A(n) = A_n(n)$. This function grows so fast that $A(4)$ is already an exponential tower of $2$'s that has height $65536$. Thus, the inverse Ackerman function, $\alpha$, grows very slowly. If $n$ is less than or equal to an exponential tower of $65536$ $2$'s, then $\alpha(n) \leq 4$. Even when it appears in exponents of the Davenport-Schinzel bounds, it does not represent a significant growth rate.

Example 6..9 (Lower Envelope of Line Segments)   One interesting application of Davenport-Schinzel applications is to the lower envelope of a set of line segments in ${\mathbb{R}}^2$. Since segments in general position may appear multiple times along the lower envelope, the total number of edges is $\Theta(\lambda_3(n)) = \Theta(n \alpha(n))$, which is higher than one would obtain from infinite lines. There are actually arrangements of segments in ${\mathbb{R}}^2$ that reach this bound; see [866]. $\blacksquare$