Advances in Applied Mechanics

1. Auflage 2014
ISBN: 978-0-12-800302-2
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, Band Volume 47, 536 Seiten

Reihe: Advances in Applied Mechanics

Advances in Applied Mechanics draws together recent significant advances in various topics in applied mechanics. Published since 1948, Advances in Applied Mechanics aims to provide authoritative review articles on topics in the mechanical sciences, primarily of interest to scientists and engineers working in the various branches of mechanics, but also of interest to the many who use the results of investigations in mechanics in various application areas, such as aerospace, chemical, civil, environmental, mechanical and nuclear engineering. - Covers all fields of the mechanical sciences - Highlights classical and modern areas of mechanics that are ready for review - Provides comprehensive coverage of the field in question

Autoren/Hrsg.

Inhaltsverzeichnis

1;Front Cover;1
2;Handbook of Computational Geometry;4
3;Copyright Page;5
4;Contents;10
5;Preface;6
6;List of Contributors;8
7;Chapter 1. Davenport–Schinzel sequences and their geometric applications;12
8;Chapter 2. Arrangements and their applications;60
9;Chapter 3. Discrete geometric shapes: Matching, interpolation, and approximation;132
10;Chapter 4. Deterministic parallel computational geometry;166
11;chapter 5. Voronoi diagrams;212
12;Chapter 6. Mesh generation;302
13;Chapter 7. Applications of computational geometry to geographic information systems;344
14;Chapter 8. Making geometry visible: An introduction to the animation of geometric algorithms;400
15;Chapter 9. Spanning trees and spanners;436
16;Chapter 10. Geometric data structures;474
17;Chapter 11. Polygon decomposition;502
18;Chapter 12. Link distance problems;530
19;Chapter 13. Derandomization in computational geometry;570
20;Chapter 14. Robustness and precision issues in geometric computation;608
21;Chapter 15. Geometric shortest paths and network optimization;644
22;Chapter 16. Randomized algorithms in computational geometry;714
23;Chapter 17. Spatial data structures: Concepts and design choices;736
24;Chapter 18. Parallel computational geometry: An approach using randomization;776
25;Chapter 19. Visibility in the plane;840
26;Chapter 20. Closest–point problems in computational geometry;888
27;Chapter 21. Graph drawing;948
28;Chapter 22. Art gallery and illumination problems;984
29;Author Index;1040
30;Subject Index;1074

Leseproben

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 l(t) : y = t (i.e., by varying t from - 8 to + 8). 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 - 8 to + 8, and maintains the xy-projection M(t) of the cross section h(t) n EC, where EC is the lower envelope of C. The projection pi, (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 l(t) and focus Then M(t) is easily seen to be the lower envelope of the parabolas pi, 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 , arranged in decreasing (i.e., clockwise) order, such that ji < i and (ji, i) ? T*, for each 1 = l = ki. Let f(T) denote the sequence T=?2??3?…??n+1. THEOREM 7.1 ([130]) Let T be a triangulation of a convex (n + 1)-gon. Then the sequence f(T) is a canonical DS(n,2)-sequence. Conversely, every canonical DS(n, 2)-sequence is the image f(T) of some triangulation T of a convex (n + 1)-gon. 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 p is called semi-free if B does not intersect the interior of any obstacle at p. 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...