Advances in Applied Mechanics (eBook)

7 Miscellaneous applications

In the previous section we presented applications of Davenport–Schinzel sequences to planar arrangements, but the scope of geometric applications of these sequences is much wider. It is beyond the scope of this survey chapter to present all these applications in detail, as they are quite diverse and require rather sophisticated and problem-specific geometric machinery. Instead, we briefly review here as many applications as space allows us, and provide more details for a few of them. More details, and additional applications, can be found in [142,153].

7.1 Applications of DS(n, 2)-sequences

Without having made it explicit, we have already encountered some combinatorial applications of DS(n, 2)-sequences in the previous sections (e.g., the analysis of the complexity of the zone of a line in an arrangement of lines). Here we present a few additional applications. See also Edelsbrunner and Guibas [57] and Ramos [125] for additional applications of this kind.

Voronoi diagrams

Let S = {p1,…, pn} be a set of n points in the plane. The Voronoi diagram of S, denoted as Vor(S), under the Euclidean metric p, is a subdivision of the plane into cells V(pi), for pi ∈ S, where V(pi) = {x ∈ 2 | ρ(x, pi) ≤ ρ(x, pj), for 1 ≤ j ≤ n}. See [24,102] for comprehensive surveys on Voronoi diagrams. Fortune [69] showed that Vor(S) can be computed efficiently by sweeping the xy-plane from bottom to top with a horizontal line ℓ(t) : y = t (i.e., by varying t from − ∞ to + ∞). The basic idea of his algorithm is as follows.

For a point pi = (x, y,) ∈ S, let

i=xyz|x−xi2+y−yi2=z2;z≥0;

this is a cone in 3-space. Let =Ci|1≤i≤n. It is easily checked that, by definition, Vor(S) is the minimization diagram of (regarding as a set of graphs of bivariate functions). The algorithm actually sweeps a slanted plane h(t) : y + z = t across 3-space, varying t from − ∞ to + ∞, and maintains the xy-projection M(t) of the cross section h(t) ∩ EC, where EC is the lower envelope of C. The projection πi, (t) of the intersection of h(t) with the cone C, is nonempty if and only if t ≥ y, and is then a parabola with directrix ℓ(t) and focus Then M(t) is easily seen to be the lower envelope of the parabolas πi, in the xy-plane. Since any two such parabolas intersect in at most 2 points, Theorem 3.1 implies that M (t) has at most 2n − 1 breakpoints. Fortune proved that, as the value of t varies, the combinatorial structure of M (t) changes at O(n) critical values of t, and that M(t) can be updated in O(log n) time at each critical value of t. Putting all these observations together, he obtained an optimal O(n log n)-time algorithm for computing Vor(S). See [69,142] for further details.

Triangulation of convex polygons

A DS(n, 2)-sequence is called canonical if its length is 2n − 1 and if its symbols are numbered so that the leftmost appearance of i precedes the leftmost appearance of j whenever i < j. Roselle [130] has shown that there exists a close relationship between triangulations of convex polygons and canonical DS(n, 2)-sequences. A triangulation T of a convex (n + l)-gon P, whose vertices are labeled 1,2,…,n + 1 in counterclockwise order, can be represented by the set T* consisting of all the diagonals (i, j), with i < j, that form T, and of the sides (i, i + 1), for 1 ≤ i ≤ n, and (1, n + 1), of P. For each vertex i of P, let ξ(i) be the sequence of all vertices 〈j1,…, jk〉, arranged in decreasing (i.e., clockwise) order, such that ji < i and (ji, i) ∈ T*, for each 1 ≤ l ≤ ki. Let φ(T) denote the sequence

T=ξ2∥ξ3∥…∥ξn+1.

It is easily verified that a convex (n + 1)-gon can be triangulated in n−2n−1/n different ways, so Theorem 7.1 implies that this is also the number of distinct canonical DS(n, 2)-sequences; see also [112]. There are several other combinatorial structures that are equivalent to canonical DS(n, 2)-sequences, including certain rooted plane trees and bracketing a formal product [98]. See [72,98] for other results on enumeration of DS(n, 2)-sequences.

7.2 Motion planning

In this subsection we describe several applications of Davenport–Schinzel sequences to algorithmic motion planning in robotics. A typical motion-planning problem can be defined as follows: we are given a robot system B with k degrees of freedom and an environment filled with obstacles. The configuration space of B is a k-dimensional parametric space, each point of which represents a possible placement of B by k-tuple of real numbers that gives the values of the parameters controlling the k degrees of freedom of B. As an example of such a configuration space, consider the case where B is a rigid polygon moving (by translations and rotations) in the plane. Here B has three degrees of freedom, and any placement of B can be represented by the triple (x, y, θ), where (x, y) are the coordinates of some fixed reference point attached to B, and θ is the orientation of B. If we allow B only to translate, it has only two degrees of freedom, and its placements can be represented by the pair (x, y) of the coordinates of the reference point.

The presence of obstacles in the robot’s environment causes portions of the configuration space of B to be “forbidden” or non-free. A placement of B is called free if B does not intersect any obstacle at that placement; otherwise it is called non-free. A non-free placement π is called semi-free if B does not intersect the interior of any obstacle at π. Our goal is to compute the free configuration space of B. which we denote by FP, consisting of all free placements of B. The boundary of FP consists of semi-free placements of B. The motion-planning problem that we consider is to determine, for any given pair of free placements, Z1, Z2, of B, whether there exists a continuous obstacle-avoiding motion of B from Z1 to Z2, and, if so, to plan such a motion.

This problem, under reasonable assumptions concerning the geometry of B and of the obstacles, can be re-stated as the problem of computing the connected components of FP, and of representing...