Amortized cost 49 195 221
Binary search 82
Convex hull, definition 81
Convex hull, dynamic 98 99
Convex hull, lower bound 98
Convex hull, order decomposable 81
Convex hull, point set 98
Convex hull, simple polygon 93
d-dimensional trees 20
Decomposable searching problem, dynamization 4
Duality 246
Dynamic planar subdivisions 135
Dynamization, decomposable 3
Dynamization, lower bounds 9
Dynamization, order decomposable 19
Dynamization, weighting 15
Hidden line elimination 227 265
Intersection, convex polygons 89
Intersection, convex polyhedra 173
Intersection, halfspaces 247
Intersection, line segments 149 230
Intersection, polygons 155 170
Intersection, rectangles 198 210
Intersection, set of lines 249
Interval trees 194
inversion 254
Least cost paths 264
Lower bounds, partial match retrieval 56
Lower bounds, polygon retrieval 66
Lower bounds, range queries 69
Lower bounds, spanning bound 60
Measure problem, polygons 241
Measure problem, rectangles 215 235
Monotone decomposable searching problem 15
Multi-dimensional searching, closest point 48
Multi-dimensional searching, divide-and-conquer 48
Multi-dimensional searching, partial match 25 29 43 56
Multi-dimensional searching, polygon queries 25 39 66
Multi-dimensional searching, range queries 25 36 69 185
Multidimensional search 25
Order decomposable searching problem 19
| Partial match 25 29 43 56
Path decomposition, plane sweep 222
Path decomposition, searching subdivisions 120
Planar subdivisions, generalized 114
Planar subdivisions, induced by lines 249
Planar subdivisions, simple 114
Plane sweep, basics 147
Plane sweep, intersecting line segments 148
Plane sweep, iso-oriented objects 186
Plane sweep, triangulation 160
Polygon tree 40
Polygon trees 40
Polygons, convex polygons, hierarchical representation 84
Polygons, convex polygons, intersection 92
Polygons, convex polygons, kernel 259
Polygons, convex polygons, separation 88
Polygons, decomposition 171
Polygons, intersection 155 170
Polygons, triangulation 160
Priority search spanning trees 199
Priority search tree 199
Range queries 25 36 69 185
Range spanning trees 43
Range tree 43
Recursion equation 50
Search, binary search 641
Searching planar subdivisions, dynamic 135
Searching planar subdivisions, independent sets 116
Searching planar subdivisions, other methods 261
Searching planar subdivisions, path decompositions 120
Segment spanning trees 212
Segment tree 212
Space sweep 173
Spanning trees 145
Transforms, duality 245
Transforms, inversion 254
Traveling salesman 145
Voronoi diagram, applications 120
Voronoi diagram, construction 103 257
Voronoi diagram, insertions, deletions 260
Voronoi diagram, merging 260
Zig-zag path decomposition 264
|
|
|
О проекте