xvi Figures
4.15 A plot of the function g as an approximation to the sgn function 85
4.16 The points in P are denoted by dots, and those in N by squares 86
5.1 Recursive Fibonacci sequence algorithm 93
5.2 The recursive unfolding of computing F
6
93
5.3 Table (a) implies that the string aba does not belong to the grammar
whereas Table (b) shows that baaba can be generated from S 96
5.4 In (a), the constant function is an average of the y values which minimizes
the sum of squares error. In (b), a 3 step function approximates the 7 point
function 99
5.5 For the label aba and starting vertex v
1
, there are several possible labeled
paths like [v
1
,v
3
,v
4
,v
6
],[v
1
,v
4
,v
5
,v
6
], etc. 101
5.6 In the sequence 13, 5, 8, 12, 9, 14, 15, 2 we have predefined the tree structure
but only the first four numbers have been scanned, i.e., 13, 5, 8, 12 104
6.1 The path traversed while searching for the element 87 111
6.2 Diagrams (a) to (d) depict the rotations required to insert the element 20
having priority 58 starting with the treap for the first four elements.
Diagram (e) is the final tree after the entire insertion sequence. Diagram (f)
shows the schematic for left/right rotations 117
6.3 The shaded leaf nodes correspond to the subset S 123
7.1 The structure of a one-dimensional range search tree where a query interval
is split into at most 2logn disjoint canonical (half)-intervals 130
7.2 The rectangle is the union of the slabs represented by the darkened nodes
plus an overhanging left segment containing p
6
132
7.3 Rectangular range query used in a k–d tree 133
7.4 Each rectangular subdivision corresponds to a node in the k–d tree and is
labeled by the splitting axis – either vertical or horizontal 134
7.5 The query is the semi-infinite upper slab supported by the two bottom
points (0, 4.5) and (10, 4.5) 137
7.6 The figure on the left is convex, whereas the one on the right is not convex 137
7.7 Convex hull of points shown as the shaded region 138
7.8 Jarvis March algorithm for convex hull 140
7.9 Merging upper hulls 141
7.10 Left turn(p
m
, p
2 j−1
, p
2 j
) is true but slope(p
2 j−1
p
2 j
) is less than the median
slope given by L 144
7.11 The shaded vertical region does not contain any intersection points 147
7.12 An example depicting Ω(n
2
) space complexity for n segments 149
7.13 Path copying technique on adjacent slabs s
5
and s
6
149
7.14 Incremental algorithm for closest pair computation 150
我的内容管理
展开
