|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| de Berg M., van Kreveld M., Overmars M. — Computational Geometry : Algorithms and applications |
|
|
|
| Предметный указатель |
 -metric 161
 -metric 148 161 316
 -metric 161
1DRANGEQUERY 97
2d-tree 100
2DBOUNDEDLP 76
2DBSP 256
2DRANDOMBSP 256
2DRANDOMIZEDBOUNDEDLP 77
2DRANDOMIZEDLP 82
2DRANGEQUERY 108
3-coloring of triangulated polygon 47 59
3DBSP 259
3DRANDOMBSP2 260
Abstract Voronoi diagram 161
Adjacency of trapezoids 127
Algorithm randomized 78
Angle of vectors in 3-space 65
Angle-optimal 186
Angle-vector 186
Approximate cell decomposition 287 288
Approximation 236
Arm robot 86
Arrangement 172 179
Arrangement in higher dimensions 179
Arrangement, complexity of 172
Arrangement, point location in 144
Arrangement, simple 172
Art Gallery Problem 45 59
Art Gallery Theorem 48
Associated structure 106 214 217 227 328 334
Auto-partition 255
Auto-partition lower bound 262
Automated manufacturing 63 90
Autonomous robot 267
Average running time 78
Axis-parallel line segment 212
Backwards analysis 79 86 89 134 141 197 242
Balanced quadtree 297
BALANCEQUADTREE 298
Ball smallest enclosing 91
Beach line 152
Binary search tree 96
Binary space partition 251 253
Binary space partition lower bound 262
Binary space partition tree 253 254
Boolean operation on polygons 39
Bounded linear program 73
Bounding box 58 124 155 223
Breakpoint 152
BSP 253
BSP lower bound 262
BSP tree 253 254
BUILD2DRANGETREE 107
BUILDKDTREE 100
C-obstacle 270
C-obstacle for translating robot 275
CAD/CAM 12 15 63 291
Canonical subset 106 109 226 323 326
Car-like robot 268
Castable 64
Casting 63
Cell decomposition approximate 287 288
Cell decomposition exact 287
Chain method point location by 143
Circle event 155
Circle event, false alarm 156
Closest pair 163
Collision 270
Collision detection 236
Coloring of triangulated polygon 47 59
Combinatorial optimization 90
Combined metric 316
Common intersection of half-planes 66 90
Composite number 111
Composite-number space 111
COMPUTEFREESPACE 271
COMPUTEPATH 273
Computer Aided Design 12 15 63 291
Computer aided manufacturing 12 15 63 90
Computer animation 236
Computer graphics 10 15 167 180
Configuration of robot 268
Configuration space 269 314
Configuration space of randomized algorithm 201
Configuration space of translating polygon 275
Configuration space, forbidden 269
Configuration space, free 269 308 314
Configuration-space 270
Configuration-space obstacle 270 314
Configuration-space obstacle for translating polygon 275
Configuration-space obstacle for translating robot 275
Conflict 240
Conflict graph 240
Conflict list 240
Conforming mesh 292 303
Connected subdivision 30
Consistent mesh 303
Constraint linear 65 66 71
Constraint linear point on circle 87
CONSTRUCTARRANGEMENT 174
CONSTRUCTINTERVALTREE 215
Continuous measure 167
Contour line 183
Convex 2
Convex combination 236
Convex hull 2 90 185 235
Convex hull computation 3 238
Convex hull lower bound 13
Convex hull pseudo code 3 6 241
Convex hull, 3-dimensional 236
Convex hull, d-dimensional 248
Convex hull, dynamic 13
Convex hull, Graham's scan 13
Convex hull, Jarvis's march 13
Convex polytope 237
Convex polytope, point location in 144
Convex set 2
convexhull 6 241
Corner vertex 294
Cutting 331 336
Cutting tree 330
Cyclic overlap 253
Data structure 211
Data structure for point location 128
Data structure, 1-dimensional range tree 99
Data structure, binary search tree 96
Data structure, BSP tree 253 254
Data structure, cutting tree 330
Data structure, heap 219
Data structure, interval tree 212 214 229
Data structure, kd-tree 100
Data structure, multi-level 327
Data structure, octree 303
Data structure, partition tree 320 322
Data structure, priority search tree 218 229
Data structure, quadtree 115 291 294
Data structure, range tree 105 109
Data structure, segment tree 223 225 229
Database 95 116
Database query 95
Davenport-Schinzel sequence 180
Decomposable searching problem 230
Decomposition, trapezoidal 124
Decomposition, vertical 124
Degeneracy 5 8 9 137
Degenerate case 5 9 137
Degree of freedom 268
Delaunay corner 206
Delaunay graph 188
| Delaunay triangulation 160 189
Delaunay triangulation computation 191
Delaunay triangulation pseudo code 192
DELAUNAYTRIANGULATION 192
Depth order 252
Design for assembly 12
Destination of half-edge 31
Diagonal of polygon 46
Difference of polygons 39
Dijkstra's algorithm 308 310 315
Direction representation of 65
Dirichlet tessellation 160
Disc smallest enclosing 86
Discrepancy 166 167 180
Discrete measure 167
Distance 161
Distance 148 161
Distance 161
Distance function 161
Distance link 316
Distance, Euclidean 148 161 316
Distance, Manhattan 161
Domain of mesh 292
Domain of terrain 183
Double wedge 170
Doubly-connected edge list 29 31 48 155 172 239
Dual graph of triangulated polygon 47
Dual of line 170
Dual of object 169
Dual of point 169
Dual of segment 170
Dual plane 170
Duality in higher dimensions 178
Duality in the plane 169
Dynamic convex hull 13
Dynamic point location 143
Dynamization 230
EDGE 30
Edge flip 186
Edge list, doubly-connected 29 31 48 155 172 239
Edge of polytope 237
Edge, illegal 186
Element of mesh 291
Elementary interval 224
Ellipse smallest enclosing 91
Embedding of graph 30
End vertex 50
Envelope lower 245
Envelope upper 246
Euclidean distance 148 161 316
Euclidean minimum spanning tree 207 209
Euler's formula 29 150 237
Event 22 51 152
Event point 22 51 152
Event queue 24 51 155
Event site 153
Event, circle 155
Exact arithmetic 9
Exact cell decomposition 287
Exact match query 116
Expectation, linearity of 79 134 197
Expected performance 78 133
Expected running time 78
Face 30
Facet 64 237
Facet top 64
Facet, ordinary 64
False alarm 156
Farthest-point Voronoi diagram 162
Fat object 264
Fat subdivision, point location in 144
Feasible point 72
Feasible region 72
Feasible solution 72
Fibonacci heap 315
FiNDlNTERSECTIONS 25
FINDNEWEVENT 27
FINDSPLITNODE 97
Finite element method 291
First-level tree 106 328
Flap 243
Flip of edge 186
Floating point, arithmetic 5
FOLLOWSEGMENT 131
Forbidden configuration space 269 314
FORBIDDENSPACE 282
Fortune's algorithm 151
Fractional cascading 109 112 143
Free configuration space 269 308 314
Free path 289
Free space 269 308 314
Free space, representation of 271
Free space, trapezoidal map of 271 308
Free split 257
Gabriel graph 207 209
General position 9 124
GENERATEMESH 301
Genus 237
Geographic information systems 1 11 15
Geometric graph 207
Geometric modeling 15
GIS 11
Graham's scan 13
Graph visibility 307
Graph, Gabriel 207 209
Graph, geometric 207
Graph, relative neighborhood 207 209
grid 116
Half-edge 31
Half-edge, destination of 31
Half-edge, origin of 31
Half-edge, record of 32
Half-plane discrepancy 167
Half-planes, common intersection of 66 90
HANDLECIRCLEEVENT 158
HANDLEENDVERTEX 53
HANDLEEVENTPOINT 26
HANDLEMERGE VERTEX 54
HANDLEREGULARVERTEX 54
HANDLESITEEVENT 158
HANDLESPLITVERTEX 54
HANDLESTARTVERTEX 53
Harmonic number 135
Heap 219
Helly-type theorem 91
Hidden surface removal 251
Higher-dimensional linear programming 82
Higher-order Voronoi diagram 162
Horizon 239
Hull convex 2 90 185 235
Hull lower 6 246
Hull upper 6 245
Illegal edge 186
Implicit point location 144
Incidence preserving 170
incident 30
Infeasible linear program 72
Infeasible point 72
Inner vertex 309
INSERTSEGMENTTREE 226
Interpolation data-independent 207
Interpolation linear 183
INTERSECTHALFPLANES 67
Intersection of half-planes 66 90
Intersection of line segments 19
Intersection of polygons 39
Intersection-sensitive algorithm 21
Interval elementary 224
Interval tree 212 274 229
inversion 179
|
|
|
| Реклама |
|
|
|
|
|
О проекте