|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Boissonnat J.D., Yvinec M. — Algorithmic Geometry |
|
|
|
| Предметный указатель |
Accelerated algorithm 88 495
Acceptable line 236
Ackermann's function 7 367
adjacency 141 252
Adjacency, graph 177 202 267
Admissible path 498
Affine, combination 134
Affine, diagram 455
Affine, hull 134
Affine, independence 134
Algorithm, accelerated 88 495
Algorithm, adaptive 5
Algorithm, divide-and-conquer 35 208 371 383 416 507
Algorithm, dynamic 99 193 227 446 508
Algorithm, incremental 182 274 308 342 343 357
Algorithm, lazy 128
Algorithm, off-line 67
Algorithm, on-line 77 348 375 414 446 447 489
Algorithm, output-sensitive 38 245
Algorithm, randomized 65
Algorithm, sweep 37 488
Alternating sequence 367
Amortized analysis 6
Analysis, amortized 6
Analysis, backward 58 93
Analysis, randomized 6 67 79 105 190 201
Annulus of minimum area 245
Arrangement of hyperplanes 333 366
Arrangement of segments 365
Arrangement of triangles 387
Arrangement, convex hull of 360
Arrangement, projective 356
Arrangement, simple 333
Arrangement, zone 337 360
Art Gallery Problem 297
Backward analysis 58 93
Ball, intersection 445
Ball, topological 253
Ball, union 445
Biregion 93 107 203
Bisection 245
Bisector of line segments 484 508
Bisector,  464
Bisector, hyperbolic 471 475
Bisector, perpendicular 423
Bitangent 210 227
Boundary of a complex 252
Boundary, non-trivial 382 383
Canonical triangulation 171 357
Caratheodory's theorem 168
Cell of an arrangement 371 404 417
Cell, complex 253 333 423 455
Co-cube 463
COMPLEX 251
Complex of cells 253 333 423 455
Complex of simplices 253
Complex, Delaunay 433
Complex, homogeneous 252
Complex, pure 252
Complex, regular 474
Complexity, average-case 4
Complexity, output-sensitive 5
Complexity, worst-case 4
Conflict 47
Conflict, graph 67
Conflict, list 73
Conformal triangulation 509
CONSTRAINED TRIANGULATION 277 312 508
Convex hull 131 134
Convex hull of a polygon 222
Convex hull of an arrangement 360
Convex hull of objects 382
Convex hull of two 3-polytopes 213
Convex hull, divide-and-conquer 212
Convex hull, dynamic 193 227
Convex hull, incremental 182
Convex hull, lower 173
Convex hull, on-line 186
Convex hull, output-sensitive 237 245
Convex hull, upper 173
Convex, function 59
Convex, set 134
Curve 44 93 384
Curve of moments 153 265
Cyclic polytope 153
Davenport — Schinzel sequences 367
Decision tree 10
Decomposition in convex parts 292 391
Decomposition of a lower envelope of triangles 397
Decomposition of a polygon 90 95 285
Decomposition of a polyhedral region 315
Decomposition of line segments 41 71 84 114
Decomposition of line segments, complete 42 92
Decomposition of line segments, dynamic 125
Decomposition of line segments, lazy 128
Decomposition of line segments, simplified 43
Decomposition of surfaces 417
Decomposition of triangles 388 408 416
Decomposition, geodesic 297
Decomposition, hierarchical 297
Decomposition, simplicial 319
Dehn — Sommerville relations 150 169 170 356
Delaunay, complex 433
Delaunay, triangulation 434
Delaunay, triangulation, flipping 439 446 447
Determinant 161 172
Determinant of a region 101 490
Determinant, van der Monde 153
Diagram for the metric 475
Diagram for the  metric 475
Diagram, affine 455
Diagram, higher order power diagram 454
Diagram, power 452 455
Diagram, weighted 457 461 474
Diameter 228
DICTIONARY 16 25
Dictionary, augmented 16 25
Dictionary, persistent 30 359
Disk 269
Disk, motion planning 497
Distance 463
Distance 466
Distance in hyperbolic space 470
Distance, point to segment 482
Distance, polygonal 507
Distance, polyhedral 475
Distance, quadratic 456
Divide-and-conquer 35 416
Divide-and-conquer, a single cell 383
Divide-and-conquer, convex hull 208 212
Divide-and-conquer, lower envelope of functions 371
Divide-and-conquer, lower envelope of triangles 416
Divide-and-conquer, union of polygons 45
Divide-and-conquer, Voronoi diagram 507
Domain of a complex 252
Domain of influence 48
Domain, feasible 232
Duality 142 268
Duality, hyperbolic diagram 476
Dynamic, algorithm 99
Dynamic, convex hull 193 227
Dynamic, decomposition of segments 125
Dynamic, perfect hashing 26 29
Dynamic, Voronoi diagram 446 508
Edge of a complex 251
Edge of a polytope 135
EMST (Euclidean minimum spanning tree) 447
Euler characteristic 258 270
Euler relation 147 170 173 258 269 270
Event queue 37
| Exterior of a polygon 256
Exterior of a polyhedron 257
Extreme points 202 235
Face of a complex 251
Face of a polytope 134 135
Face of a Voronoi diagram 457 464 466 470 482
Face of an arrangement 356 366 388
Face, inner 404
Face, outer 404
Face, popular 404
Face, proper 135
Face, singular 253
Facet of a polytope 135
Feasible domain 232
Function Ackermann 7 367
Function, convex 59
Function, hash function 29
General position for hyperplanes 146 333
General position for points 146
General position for spheres 453
General position, -general 475
General position,  -general 424 482
General position, -general 467 475
Geodesic decomposition 297
Gift-wrapping 213
Graph 16
Graph of adjacencies 177 202 267
Graph of conflicts 67
Graph of incidences 176 267
Graph of influence 78
Graph of influence (augmented) 101
Greatest empty rectangle 473
Hashing, hash functions 29
Hashing, perfect dynamic 26 29
Helly's theorem 168
Hierarchical decomposition 297
Hierarchical representation 228 293
history 96
Homogeneous complex 252
Hull, affine 134
Hull, convex 131 134
Hull, lower 173
Hull, upper 173
Hyperbolic bisector 475
Hyperbolic duality 476
Hyperbolic space 470 476
Hyperbolic Voronoi diagram 470 508
Hyperplane, arrangement 333
Hyperplane, radical 430
Hyperplane, supporting 135 169
incidence 141 252
Incidence, graph 176 267 269
Incremental arrangement 342 343 357
Incremental convex hull 182
Incremental triangulation 274 308
Independence, affine 134
Influence, domain 48
Influence, graph 78
Influence, graph (augmented) 101
Inner face 404
Inner vertex 62
Interior of a polygon 256
Interior of a polyhedron 257
Interior of a polytope 134
Interior of a sphere 425
Intersection of balls 445
Intersection of convex polygons 229
Intersection of half-spaces 173 203 245
Intersection of line segments 38
Intersection of polygonal regions 44
Intersection, miscellaneous 229
Jordan's Theorem 268
k-set 347 361
k-th element (selection of) 45
Lazy decomposition of segments 128
Lazy sweeping 290
Level in arrangements of hyperplanes 346 361 362
Level in arrangements of lines 361
Level in arrangements of simplices 417
Level in arrangements of triangles 417
Level in arrangements, surface of 346
Linear programming 231
LIST 14
Localization in a planar map 293
Lower envelope of cones 473
Lower envelope of functions 368
Lower envelope of half-lines 371
Lower envelope of line segments 370 381
Lower envelope of simplices 416
Lower envelope of surfaces 416
Lower envelope of triangles 393
Lower hull 173
LP-type problems 247
Mapping, projective 157
Maximal polytope 172
Maximum inscribed sphere 247
Minimum enclosing circle 246 445
Minkowski sum 174
moment 56
Moment, curve 153 265
Moment, theorem 57
Monotone polygon 279
Motion planning of a disk 497
Motion planning of a manipulator 384
Motion planning of a polygon 382 508
Motion planning of a polyhedron 418
Nearest neighbor 444 445
Nearest neighbor, on-line 445
Nearest neighbor, queries 444
Non-local subset of regions 59
Non-trivial boundary 382 383
Object 47
Off-line algorithm 67
On-line,  k-levels 348
On-line, a single cell 375 414
On-line, algorithm 77
On-line, convex hull 186
On-line, decomposition of line segments 84
On-line, Delaunay triangulation 446 447
On-line, Voronoi diagram 432 446 489
Onion peeling 228
Orientation in a projective space 161
Orientation of a 2-triangulation 257
Orientation, clockwise and counter-clockwise 206 207
Orientation, direct and indirect 206 207
Orthogonal spheres 428
Outer face 404
Outer vertex 62
Output-sensitive, complexity 5
Output-sensitive, convex hull 237 245
Output-sensitive, segment intersections 38
Output-sensitive, triangulation 312
Paraboloid 172 426
Pencil of spheres 468
Perpendicular bisector 423
Persistent dictionary 30 359
Planar map 269
Poincare disk 476
Poincare half-space 470
Polarity with respect to a paraboloid 172 427
Polarity, image 142
Polarity, polytope 143
Polarity, projective 157
Polarity, transformation 141
Polygon 256
Polygon, convex hull of 222
Polygon, decomposition of 90 95
Polygon, intersection 44
Polygon, monotone 279
Polygon, star-shaped 294
|
|
|
| Реклама |
|
|
|
|
|
О проекте