Handbook of Discrete and Computational Geometry

Handbook of Discrete and Computational Geometry, Second Edition......Page 6
Discrete Mathematics and ITS Applications......Page 3
PREFACE......Page 8
PREFACE TO THE SECOND EDITION......Page 10
CONTRIBUTORS......Page 14
CONTENTS......Page 12
GLOSSARY......Page 19
SYLVESTER-TYPE RESULTS......Page 20
MIXED PROBLEMS......Page 22
1.2 METRIC PROBLEMS......Page 25
REPEATED DISTANCES......Page 26
DISTINCT DISTANCES......Page 28
RELATED RESULTS......Page 29
CONJECTURES OF ERDOS......Page 30
GLOSSARY......Page 31
FORBIDDEN DISTANCES......Page 32
OPEN PROBLEMS......Page 33
RELATED CHAPTERS......Page 34
REFERENCES......Page 35
GLOSSARY......Page 41
KNOWN VALUES OF PACKING AND COVERING DENSITIES......Page 43
THE KEPLER CONJECTURE......Page 45
EXISTENCE OF ECONOMICAL ARRANGEMENTS......Page 47
UPPER BOUNDS FOR Æ(Bd) AND LOWER BOUNDS FOR #(Bd)......Page 48
PACKING IN AND COVERING OF A BODY WITH GIVEN SHAPE......Page 49
SAUSAGE CONJECTURES......Page 52
GLOSSARY......Page 53
SPHERICAL SPACE......Page 56
HYPERBOLIC SPACE......Page 57
GLOSSARY......Page 60
2.6 SELECTED PROBLEMS ON LATTICE ARRANGEMENTS......Page 61
2.7 PACKING AND COVERING WITH SEQUENCES OF CONVEX BODIES......Page 62
REFERENCES......Page 64
GLOSSARY......Page 69
MAIN RESULTS......Page 71
GLOSSARY......Page 72
MAIN RESULTS......Page 74
OPEN PROBLEMS......Page 75
GLOSSARY......Page 76
GLOSSARY......Page 77
MAIN RESULTS......Page 80
3.4 NONPERIODIC AND APERIODIC TILINGS......Page 81
GLOSSARY......Page 82
MAIN RESULTS......Page 83
3.5 OTHER TILINGS......Page 84
RELATED CHAPTERS......Page 85
REFERENCES......Page 86
GLOSSARY......Page 89
4.1.1 GENERALIZATIONS TO NONCONVEX SETS......Page 90
4.1.2 INTERSECTIONS IN MORE THAN A POINT......Page 91
4.1.3 REDUCING d+1......Page 92
RESULTS......Page 94
4.1.6 RELATED THEOREMS......Page 95
4.1.7 RELATED ALGORITHMS......Page 96
GLOSSARY......Page 97
NOTATION......Page 98
4.2.1 HADWIGER'S TRANSVERSAL THEOREM......Page 99
GLOSSARY......Page 100
4.2.4 TRANSLATES......Page 101
4.2.6 SPACE OF TRANSVERSALS......Page 103
4.2.7 GEOMETRIC PERMUTATIONS......Page 104
4.2.9 CONVEXITY ON THE AFFINE GRASSMANNIAN......Page 106
4.2.10 OPEN PROBLEMS......Page 107
RELATED CHAPTERS......Page 108
REFERENCES......Page 109
GLOSSARY......Page 113
GLOSSARY......Page 116
ARRANGEMENTS OF STRAIGHT LINES......Page 117
CONFIGURATIONS OF POINTS......Page 119
ALLOWABLE SEQUENCES......Page 120
LOCAL SEQUENCES AND CLUSTERS OF STARS......Page 121
STRETCHABLE AND NONSTRETCHABLE ARRANGEMENTS......Page 122
GLOSSARY......Page 124
RELATIONS AMONG NUMBERS OF VERTICES, EDGES, AND FACES......Page 125
THE NUMBER OF CELLS OF DIFFERENT SIZES......Page 126
SIMPLICIAL ARRANGEMENTS......Page 128
COMPLEXITY OF SETS OF CELLS IN AN ARRANGEMENT......Page 129
GLOSSARY......Page 130
EMBEDDING IN LARGER STRUCTURES......Page 131
MOVING FROM ONE ARRANGEMENT TO ANOTHER......Page 132
THE NUMBER OF ARRANGEMENTS......Page 133
HOW MUCH SPACE IS NEEDED TO SPECIFY AN ARRANGEMENT?......Page 134
REALIZABILITY......Page 135
GLOSSARY......Page 136
APPLICATIONS OF DUALITY......Page 137
PSEUDOTRIANGULATIONS......Page 138
RELATED CHAPTERS......Page 139
REFERENCES......Page 140
GLOSSARY......Page 145
GLOSSARY......Page 147
GLOSSARY......Page 148
GLOSSARY......Page 149
6.2 AXIOMS AND REPRESENTATIONS......Page 150
GLOSSARY......Page 151
6.2.2 COCIRCUITS......Page 152
GLOSSARY......Page 153
GLOSSARY......Page 154
GLOSSARY......Page 155
6.2.6 AN EXAMPLE......Page 156
GLOSSARY......Page 158
GLOSSARY......Page 159
CONSEQUENCES OF THE UNIVERSALITY THEOREM......Page 160
TRIANGLES IN ARRANGEMENTS OF PSEUDOLINES......Page 161
SIMPLICIAL CELLS IN PSEUDOARRANGEMENTS......Page 162
6.3.4 MATROID POLYTOPES......Page 163
ALGORITHMIC APPROACH TO POLYTOPE CLASSIFICATION......Page 164
RELATED CHAPTERS......Page 165
REFERENCES......Page 166
GLOSSARY......Page 168
V-POLYTOPES WITH MANY VERTICES......Page 169
CONVEX HULL OF INTEGRAL POINTS......Page 170
FLATNESS THEOREMS......Page 171
MINKOWSKI'S CONVEX BODY THEOREM......Page 172
7.3 COUNTING PROBLEM......Page 173
SOME EXPLICIT FORMULAS IN LOW DIMENSIONS......Page 174
EXPONENTIAL SUMS OVER RATIONAL POLYHEDRA......Page 175
THE IDEA OF THE ALGORITHM......Page 177
CONNECTIONS WITH TORIC VARIETIES......Page 178
CONNECTIONS WITH VALUATIONS......Page 179
ANALYTICAL METHODS......Page 180
PROBABILISTIC METHODS......Page 181
GLOSSARY......Page 182
GENERAL PROPERTIES......Page 183
EULER-MACLAURIN FORMULAS......Page 184
THE h -VECTOR......Page 185
INTEGRAL POINTS IN RATIONAL POLYTOPES......Page 186
PROBLEM WITH QUANTIFIERS......Page 187
REFERENCES......Page 188
INTRODUCTION......Page 192
8.1.1 THE EUCLIDEAN SPACES Ld 2......Page 193
GLOSSARY......Page 194
8.1.3 THE OTHER p......Page 195
8.2.2 THE DIMENSION OF EMBEDDINGS IN L......Page 196
8.2.3 THE JOHNSON-LINDENSTRAUSS LEMMA: FLATTENING IN L2......Page 197
GLOSSARY......Page 198
PLANAR-GRAPH METRICS AND OTHER CLASSES WITH A FORBIDDEN MINOR......Page 199
EARTH-MOVER DISTANCE (EMD)......Page 200
GLOSSARY......Page 201
8.4.1 PROBABILISTIC EMBEDDINGS IN TREES......Page 202
8.4.2 RAMSEY-TYPE THEOREMS......Page 203
8.5 ALGORITHMIC APPLICATIONS OF EMBEDDINGS......Page 204
REFERENCES......Page 208
GLOSSARY......Page 212
CONNECTIVITY......Page 214
9.3 CONFIGURATION SPACES WITHOUT SELF-INTER- SECTIONS......Page 215
WHICH LINKAGES ARE LOCKED?......Page 216
UNLOCKED LINKAGES......Page 217
SPECIAL CLASSES OF LINKAGES......Page 219
FLIPS AND FLIPTURNS......Page 220
TRACING CURVES......Page 221
ARBITRARY CONFIGURATION SPACES......Page 222
HARDNESS RESULTS......Page 223
ALGORITHMS......Page 224
FOUR-BAR MECHANISM......Page 225
FURTHER READING......Page 226
APPLICATIONS IN BIOLOGY......Page 227
REFERENCES......Page 229
GLOSSARY......Page 234
CROSSING-FREE GEOMETRIC GRAPHS......Page 235
TURAN-TYPE PROBLEMS......Page 236
RAMSEY-TYPE PROBLEMS......Page 238
OPEN PROBLEMS......Page 239
GLOSSARY......Page 240
GENERAL ESTIMATES......Page 241
OPEN PROBLEMS......Page 243
10.3 GENERALIZATIONS......Page 244
TOPOLOGICAL GRAPHS......Page 245
GEOMETRIC HYPERGRAPHS......Page 246
SURVEYS......Page 248
REFERENCES......Page 249
11.1 r-RAMSEY SETS......Page 254
GLOSSARY......Page 257
GLOSSARY......Page 259
11.4 EDGE-RAMSEY SETS......Page 260
11.5 HOMOTHETIC RAMSEY SETS AND DENSITYTHEOREMS......Page 261
GLOSSARY......Page 263
ASYMMETRIC RAMSEY THEOREMS......Page 264
PARTITIONS WITH INFINITELY MANY PARTS......Page 265
COMPLEXITY ISSUES......Page 266
REFERENCES......Page 267
GLOSSARY......Page 270
12.1.2 NATURAL DISTRIBUTIONS......Page 271
12.1.3 UNIFORM RANDOM POINTS IN CONVEX BODIES......Page 272
OPEN PROBLEMS......Page 277
OPEN PROBLEM......Page 278
12.1.5 CONVEX HULLS FOR OTHER DISTRIBUTIONS......Page 279
12.2.1 GEOMETRIC CONFIGURATIONS......Page 280
GLOSSARY......Page 281
12.3.1 RANDOM HYPERPLANES AND HALFSPACES......Page 282
12.3.2 RANDOM FLATS THROUGH CONVEX BODIES......Page 283
12.4 RANDOM CONGRUENT COPIES......Page 284
12.5.1 GENERAL MOSAICS......Page 285
12.5.2 HYPERPLANE TESSELLATIONS......Page 286
SOURCES FOR STOCHASTIC GEOMETRY IN GENERAL......Page 287
RELEVANT SURVEYS AND FURTHER SOURCES......Page 288
REFERENCES......Page 289
GLOSSARY......Page 294
PROBABILITY MEASURES AND DISCREPANCY......Page 297
13.3 ALIGNED RECTANGLES IN THE UNIT SQUARE......Page 298
13.4 ALIGNED BOXES IN A UNIT k-CUBE......Page 300
13.5 MOTION-INVARIANT PROBLEMS......Page 303
GLOSSARY......Page 304
13.8 WORK OF MONTGOMERY......Page 306
GLOSSARY......Page 307
13.10 BOUNDARIES OF GENERATORS FORHOMOTHETICALLY INVARIANT J......Page 309
GLOSSARY......Page 310
13.11 D(K,J,2,N) IN LIGHT OF DISTANCE GEOMETRY......Page 311
GLOSSARY......Page 313
REFERENCES......Page 315
WHERE HAS TOPOLOGY BEEN APPLIED IN COMPUTER SCIENCE?......Page 320
GLOSSARY......Page 321
14.2.1 THE HAM SANDWICH THEOREM......Page 324
TOPOLOGICAL BACKGROUND......Page 325
TOPOLOGICAL BACKGROUND......Page 326
TOPOLOGICAL BACKGROUND......Page 327
APPLICATIONS AND RELATED RESULTS......Page 328
14.2.5 RADIAL PARTITIONS BY POLYHEDRAL FANS......Page 329
14.2.7 PARTITIONS BY CONVEX SETS......Page 330
14.2.9 OTHER EQUIPARTITIONS......Page 331
14.3.1 BORSUK'S PROBLEM......Page 332
14.3.2 KNASTER'S PROBLEM......Page 333
GLOSSARY......Page 334
APPLICATIONS AND RELATED RESULTS......Page 335
14.4.2 COLORED TVERBERG THEOREMS......Page 336
OTHER RELATED RESULTS......Page 338
GLOSSARY......Page 339
FURTHER READING......Page 340
REFERENCES......Page 341
GLOSSARY......Page 345
GLOSSARY......Page 346
15.3 HOW MANY n-OMINOES ARE THERE?......Page 348
UNSOLVED PROBLEMS......Page 349
GLOSSARY......Page 350
COMPOSITIONS AND ROW-CONVEX POLYOMINOES......Page 352
ROW-COLUMN-CONVEX POLYOMINOES......Page 353
WIDTH-k POLYOMINOES......Page 354
DIRECTED POLYOMINOES......Page 355
GLOSSARY......Page 356
15.7 RECTANGLES OF POLYOMINOES......Page 359
REFERENCES......Page 365
GLOSSARY......Page 367
GLOSSARY......Page 370
GLOSSARY......Page 372
GLOSSARY......Page 373
GLOSSARY......Page 375
ZONOTOPES......Page 376
CYCLIC POLYTOPESCyclic polytopes can......Page 377
OPEN PROBLEMS......Page 378
GLOSSARY......Page 379
OPEN PROBLEMS......Page 380
GLOSSARY......Page 381
GLOSSARY......Page 383
16.2 METRIC PROPERTIES......Page 384
GLOSSARY......Page 385
GLOSSARY......Page 386
GLOSSARY......Page 388
SOME COMPUTATIONS......Page 390
AN APPLICATION......Page 391
REFERENCES......Page 392
GLOSSARY......Page 395
GLOSSARY......Page 396
MAIN RESULTS......Page 397
EXAMPLES......Page 398
MAIN RESULTS......Page 399
17.3.1 TRIANGULATING REGIONS BETWEEN POLYTOPES......Page 401
GLOSSARY......Page 402
MAIN RESULTS......Page 403
EXAMPLES......Page 404
MAIN RESULTS......Page 405
MAIN RESULTS......Page 406
MAIN RESULTS......Page 407
GLOSSARY......Page 408
MAIN RESULTS......Page 409
EXAMPLES......Page 410
17.5.4 COMPLETE BARYCENTRIC SUBDIVISIONS......Page 411
GLOSSARY......Page 412
MAIN RESULTS......Page 413
17.6.1 FIBER POLYTOPES......Page 414
FURTHER READING......Page 415
REFERENCES......Page 416
GLOSSARY......Page 419
THE KRUSKAL-KATONA THEOREM AND SOME RELATIVES......Page 420
MULTICOMPLEXES AND MACAULAY'S THEOREM......Page 421
GLOSSARY......Page 422
COHEN-MACAULAY COMPLEXES......Page 423
LERAY COMPLEXES......Page 424
GLOSSARY......Page 425
PSEUDOMANIFOLDS......Page 426
POLYTOPES AND SPHERES......Page 427
COMMENTS......Page 428
BASIC f -VECTOR RELATIONS......Page 429
COMMENTS......Page 430
GLOSSARY......Page 431
LINEAR INEQUALITIES......Page 432
HYPERPLANE ARRANGEMENTS AND ZONOTOPES......Page 434
GENERAL 3- AND 4-POLYTOPES......Page 435
COMMENTS......Page 436
18.6 OPEN PROBLEMS......Page 437
REFERENCES......Page 439
GLOSSARY......Page 443
ENUMERATION AND CONSTRUCTION......Page 445
SYMMETRY GROUPS......Page 446
GLOSSARY......Page 447
ENUMERATION AND CONSTRUCTION......Page 448
GLOSSARY......Page 449
ENUMERATION......Page 450
19.4 THE GRUNBAUM-DRESS POLYHEDRA......Page 451
ENUMERATION......Page 452
GLOSSARY......Page 453
19.6 REFLECTION GROUPS......Page 454
GENERAL PROPERTIES......Page 455
ENUMERATION AND GROUPS......Page 457
GLOSSARY......Page 459
GENERAL PROPERTIES......Page 460
CLASSIFICATION BY TOPOLOGICAL TYPE......Page 461
REALIZATIONS......Page 462
SURVEYS......Page 463
REFERENCES......Page 464
GLOSSARY......Page 467
GLOSSARY......Page 469
SUBGRAPHS AND INDUCED SUBGRAPHS......Page 470
CONNECTIVITY AND SEPARATION......Page 471
EXPANSION......Page 472
GLOSSARY......Page 473
20.4 POLYTOPAL DIGRAPHS......Page 475
GLOSSARY......Page 476
SHELLABILITY AND COLLAPSIBILITY......Page 477
FACET-FORMING POLYTOPES AND SMALL LOW-DIMENSIONAL FACES......Page 478
RECONSTRUCTION......Page 480
EMPTY FACES AND POLYTOPES WITH FEW VERTICES......Page 482
RELATED CHAPTERS......Page 483
REFERENCES......Page 484
GLOSSARY......Page 489
BASIC RESULTS......Page 491
BASIC RESULTS......Page 493
EBERHARD-TYPE RESULTS......Page 496
GENERAL RESULTS......Page 498
GENERAL RESULTS......Page 499
RELATED CHAPTERS......Page 501
REFERENCES......Page 502
GLOSSARY......Page 504
POLARITY......Page 505
GLOSSARY......Page 506
THE SIZES OF COMBINATORIAL DESCRIPTIONS......Page 507
MAIN RESULTS AND OPEN PROBLEMS......Page 509
22.3.1 THE INCREMENTAL METHOD......Page 510
22.3.2 THE GRAPH TRAVERSAL METHOD......Page 512
THE GENERAL CASE......Page 513
THE PRIMAL-DUAL METHOD......Page 514
THE 2-DIMENSIONAL CASE......Page 515
22.5 RELATED TOPICS......Page 516
REFERENCES......Page 518
GLOSSARY......Page 522
RELATION TO CONVEXITY......Page 524
23.2 BASIC ALGORITHMS......Page 525
THE RANDOMIZED INCREMENTAL ALGORITHM......Page 526
OTHER ALGORITHMS......Page 527
HIGHER-ORDER VORONOI DIAGRAMS......Page 528
CONFORMING DELAUNAY TRIANGULATIONS......Page 529
OTHER DISTANCE MEASURES......Page 530
KINETIC VORONOI DIAGRAMS......Page 531
IMPLEMENTATIONS......Page 532
VISIBILITY DEPTH ORDERING......Page 533
FURTHER READING......Page 534
REFERENCES......Page 535
GLOSSARY......Page 538
COUNTING CELLS......Page 539
PLANAR ARRANGEMENTS......Page 540
THREE AND HIGHER DIMENSIONS......Page 541
GLOSSARY......Page 542
COMBINATORIAL COMPLEXITY BOUNDS FOR SUBSTRUCTURES......Page 544
UNION BOUNDARY......Page 545
ADDITIONAL COMBINATORIAL BOUNDS......Page 546
24.3 REPRESENTATIONS AND DECOMPOSITIONS......Page 547
SKELETON......Page 548
BOTTOM VERTEX DECOMPOSITION OF HYPERPLANE ARRANGEMENTS......Page 549
VERTICAL DECOMPOSITION......Page 550
24.4 ALGORITHMS FOR ARRANGEMENTS......Page 551
24.4.1 DETERMINISTIC ALGORITHMS......Page 552
24.4.2 RANDOMIZED ALGORITHMS......Page 554
LOWER ENVELOPE......Page 555
MANY CELLS......Page 556
ARRANGEMENTS OF CONVEX POLYTOPES......Page 557
EXAMPLE: MINIMUM AREA TRIANGLE......Page 558
OTHER APPLICATIONS......Page 559
EXACT COMPUTING......Page 560
APPROXIMATE ARITHMETIC IN PREDICATE EVALUATION......Page 561
OPEN PROBLEM......Page 562
2D ARRANGEMENTS IN CGAL......Page 563
RELATED CHAPTERS......Page 564
REFERENCES......Page 565
GLOSSARY......Page 572
ALGORITHMS......Page 573
OPTIMALITY PROPERTIES......Page 574
SIMPLE POLYGONS......Page 575
PLANAR STRAIGHT-LINE GRAPHS......Page 576
25.3 OPTIMAL TRIANGULATIONS......Page 577
EDGE FLIPPING AND EDGE INSERTION......Page 578
MINIMUM WEIGHT TRIANGULATION......Page 579
NO SMALL ANGLES......Page 580
NO LARGE ANGLES......Page 581
SURFACE MESHES......Page 582
GLOSSARY......Page 583
GENERAL POLYHEDRA......Page 584
THREE-DIMENSIONAL MESH GENERATION......Page 585
GLOSSARY......Page 586
POLYTOPES......Page 587
RELATED CHAPTERS......Page 588
REFERENCES......Page 589
GLOSSARY......Page 592
POLYGON TYPES......Page 593
GLOSSARY......Page 594
TRIANGULATION......Page 595
COVERS AND PARTITIONS......Page 596
ORTHOGONAL POLYGONS......Page 597
AREA BISECTION......Page 598
DISSECTIONS......Page 599
26.3 POLYGON INTERSECTION......Page 600
EUCLIDEAN MEASURE......Page 601
LINK MEASURE......Page 603
VISIBILITY AND RAY SHOOTING......Page 604
CONTAINMENT OF POLYGONS......Page 605
INSCRIBING/CIRCUMSCRIBING POLYGONS......Page 606
POLYGON MORPHING......Page 607
CSG REPRESENTATION......Page 608
THREE-DIMENSIONAL POLYGONS......Page 609
REFERENCES......Page 610
INTRODUCTION......Page 616
GLOSSARY......Page 617
27.1 PATHS IN A SIMPLE POLYGON......Page 618
TWO-POINT QUERIES......Page 619
OPEN PROBLEMS......Page 620
CONTINUOUS DIJKSTRA METHOD......Page 621
TWO-POINT QUERIES......Page 622
OTHER RESULTS......Page 623
GLOSSARY......Page 624
LINK DISTANCE......Page 625
L1 METRIC......Page 626
WEIGHTED REGION METRIC......Page 627
MINIMUM-TIME PATHS......Page 628
OPTIMAL ROBOT MOTION......Page 629
OPEN PROBLEMS......Page 630
GLOSSARY......Page 631
TRAVELING SALESMAN PROBLEM......Page 632
WATCHMAN ROUTE PROBLEM......Page 633
GLOSSARY......Page 634
SPECIAL CASES......Page 635
APPROXIMATION ALGORITHMS......Page 636
OTHER METRICS......Page 637
GLOSSARY......Page 638
t-SPANNERS......Page 640
PLANAR t-SPANNERS......Page 641
SURVEYS......Page 642
REFERENCES......Page 643
GLOSSARY......Page 651
COVERS AND PARTITIONS......Page 652
28.1.1 FLOODLIGHT ILLUMINATION......Page 653
MAIN RESULTS......Page 654
GOALS......Page 655
VERTEX VISIBILITY GRAPHS......Page 656
OPEN PROBLEMS......Page 657
VISIBILITY POLYGON ALGORITHM......Page 658
ENDPOINT VISIBILITY GRAPH......Page 659
MAIN RESULTS......Page 660
GLOSSARY......Page 661
28.8.2 BINARY SPACE PARTITION TREES......Page 662
ALGORITHMS......Page 664
28.9 PENETRATING ILLUMINATION OF CONVEX BODIES......Page 665
GLOSSARY......Page 666
REFERENCES......Page 667
29.1 STATIC RECONSTRUCTION PROBLEMS......Page 672
GLOSSARY......Page 673
GLOSSARY......Page 675
MAIN RESULTS......Page 676
COMPUTER VISION......Page 678
TOMOGRAPHY AND SURFACES FROM CROSS-SECTIONS AND PROJECTIONS......Page 679
SURVEYS......Page 680
REFERENCES......Page 681
GLOSSARY......Page 684
GLOSSARY......Page 685
NONUNIFORM SAMPLE......Page 686
NONSMOOTHNESS, BOUNDARIES......Page 687
30.2 SURFACE RECONSTRUCTION......Page 688
GLOSSARY......Page 689
CRUST......Page 690
COCONE......Page 691
NATURAL NEIGHBOR......Page 692
WATERTIGHT SURFACES......Page 693
OPEN PROBLEMS......Page 694
GLOSSARY......Page 695
MAIN RESULTS......Page 696
REFERENCES......Page 697
INTRODUCTION......Page 700
REFERENCES......Page 701
GLOSSARY......Page 702
31.1.1 CONVERSION OF ONE PRESENTATION INTO THE OTHER......Page 703
RELATED CHAPTERS......Page 704
GLOSSARY......Page 705
FURTHER READING......Page 706
GLOSSARY......Page 707
31.3.1 CLASSICAL BACKGROUND, CHARACTERIZATIONS......Page 708
31.3.2 SOME VOLUME FORMULAS......Page 709
31.3.3 TRACTABILITY RESULTS......Page 710
31.3.6 RANDOMIZED ALGORITHMS......Page 711
RELATED CHAPTERS......Page 712
GLOSSARY......Page 713
31.4.3 INTRACTABILITY RESULTS......Page 714
31.4.4 RANDOMIZED ALGORITHMS......Page 715
REFERENCES......Page 716
31.5.2 OPTIMAL CONTAINMENT UNDER HOMOTHETY......Page 717
31.5.3 OPTIMAL CONTAINMENT UNDER AFFINITY: SIMPLICES......Page 718
31.5.4 OPTIMAL CONTAINMENT UNDER AFFINITY: ELLIPSOIDS......Page 719
REFERENCES......Page 720
APPLICATIONS......Page 721
REFERENCES......Page 722
GLOSSARY......Page 723
TRACTABILITY RESULTS......Page 724
REFERENCES......Page 725
GLOSSARY......Page 726
BASIC TOPOLOGICAL PROBLEMS AND APPLICATIONS......Page 727
GLOSSARY......Page 728
BASIC PROPERTIES......Page 730
OPEN PROBLEMS......Page 731
EXAMPLES AND ELEMENTARY PROPERTIES......Page 732
32.4 ALGEBRAIC TOPOLOGY......Page 733
GLOSSARY......Page 734
32.4.2 HOMOTOPY GROUPS......Page 735
EXAMPLES......Page 736
ALGORITHMS AND COMPLEXITY......Page 737
BASIC RESULTS......Page 738
MAIN RESULTS......Page 739
ALGORITHMS AND COMPLEXITY......Page 740
BASIC RESULTS......Page 741
GLOSSARY......Page 742
EXAMPLES......Page 744
BASIC RESULTS......Page 745
FURTHER READING......Page 746
REFERENCES......Page 747
33.1 FIRST-ORDER THEORY OF REALS......Page 750
GLOSSARY......Page 751
QUANTIFIER ELIMINATION PROBLEM......Page 752
TARSKI-SEIDENBERG THEOREM......Page 754
GLOSSARY......Page 755
33.3 REAL ALGEBRAIC NUMBERS......Page 756
GLOSSARY......Page 757
STURM-SYLVESTER THEOREM......Page 758
GLOSSARY......Page 759
33.4 UNIVARIATE DECOMPOSITION......Page 760
GLOSSARY......Page 761
CONSTRUCTING SAMPLE POINTS......Page 762
COLLINS'S APPROACH......Page 763
NEW APPROACHES USING CRITICAL POINTS......Page 764
33.7 APPLICATIONS......Page 765
OFFSET SURFACE CONSTRUCTION IN SOLID MODELING......Page 766
CONNECTION TO SEMIDEFINITE PROGRAMMING......Page 767
SURVEYS......Page 768
REFERENCES......Page 769
GLOSSARY......Page 772
LIST SEARCH AS ONE-DIMENSIONAL POINT LOCATION......Page 773
GLOSSARY......Page 774
SLABS AND PERSISTENCE......Page 775
TRAPEZOID GRAPH METHODS......Page 777
TRIANGULATIONS......Page 779
GLOSSARY......Page 780
DYNAMIC INTERVAL TREE......Page 781
OPEN PROBLEMS......Page 782
SUBDIVISION WALKING......Page 783
THREE-DIMENSIONAL POINT LOCATION......Page 784
OPEN PROBLEMS......Page 785
IMPLICIT POINT LOCATION......Page 786
REFERENCES......Page 787
PROBLEM CLASSIFICATION......Page 791
MINKOWSKI SUMS AND CONVEX OPTIMIZATION......Page 794
TRACKING CLOSEST FEATURES USING GEOMETRIC LOCALITY AND MOTION COHERENCE......Page 795
35.2 GENERAL POLYGONAL MODELS......Page 796
SEPARATION-DISTANCE COMPUTATION......Page 797
QUERIES ON BOUNDING VOLUMES......Page 798
35.3 PENETRATION-DEPTH COMPUTATION......Page 799
CONVEX POLYTOPES......Page 800
35.4 SPLINE AND ALGEBRAIC OBJECTS......Page 801
35.5 DYNAMIC QUERIES......Page 802
35.6 LARGE ENVIRONMENTS......Page 803
35.7 PROXIMITY QUERY PACKAGES......Page 805
RELATED CHAPTERS......Page 806
REFERENCES......Page 807
INTRODUCTION......Page 812
36.1 MODELS OF COMPUTATION......Page 813
36.2 ORTHOGONAL RANGE SEARCHING......Page 816
UPPER BOUNDS......Page 817
LOWER BOUNDS......Page 818
SECONDARY MEMORY STRUCTURES......Page 819
LINEAR-SIZE DATA STRUCTURES......Page 820
36.3 SIMPLEX RANGE SEARCHING......Page 822
LINEAR-SIZE DATA STRUCTURES......Page 823
DATA STRUCTURES WITH LOGARITHMIC QUERY TIME......Page 824
LOWER BOUNDS......Page 825
OPEN PROBLEMS......Page 826
MULTI-LEVEL STRUCTURES......Page 827
SEMIALGEBRAIC RANGE SEARCHING......Page 828
KINETIC RANGE SEARCHING......Page 829
OPEN PROBLEMS......Page 830
POINT INTERSECTION SEARCHING......Page 831
SEGMENT INTERSECTION SEARCHING......Page 832
RAY-SHOOTING QUERIES......Page 833
RELATED READING......Page 835
REFERENCES......Page 836
INTRODUCTION......Page 841
GLOSSARY......Page 842
GLOSSARY......Page 844
GLOSSARY......Page 845
GLOSSARY......Page 847
GLOSSARY......Page 848
OFF-LINE RAY SHOOTING IN AN ARBITRARY DIRECTION......Page 849
EXTENSIONS AND ALTERNATIVE METHODS......Page 850
ARBITRARY MOTIONS......Page 851
GLOSSARY......Page 852
GLOSSARY......Page 853
REFERENCES......Page 855
GLOSSARY......Page 859
GLOSSARY......Page 860
INTERSECTION DETECTION OF CONVEX POLYGONS......Page 861
SIMPLE POLYGONS......Page 862
INTERSECTION DETECTION WITH PREPROCESSING......Page 863
INTERSECTION DETECTION ALGORITHM......Page 864
GLOSSARY......Page 865
REPORTING LINE SEGMENT INTERSECTIONS......Page 866
RED-BLUE INTERSECTION PROBLEMS......Page 867
COUNTING LINE SEGMENT INTERSECTIONS......Page 868
INTERSECTION SEARCHING AND RANGE SEARCHING......Page 869
CONVEX POLYGONS......Page 870
SIMPLE POLYGONS AND CLIPPING......Page 871
INTERSECTION CONSTRUCTION IN HIGHER DIMENSIONS......Page 872
GRIDS......Page 873
38.6 SOURCES......Page 874
REFERENCES......Page 875
INTRODUCTION......Page 879
GLOSSARY......Page 880
RANDOM PROJECTION APPROACH......Page 881
DIVIDE-AND-CONQUER APPROACH......Page 883
AVERAGE-CASE ALGORITHMS......Page 884
GLOSSARY......Page 885
39.3 LOWER BOUNDS......Page 888
GLOSSARY......Page 889
REDUCTIONS......Page 890
39.4 LOW VS. HIGH DIMENSIONS IN COMPUTATIONAL GEOMETRY......Page 891
REFERENCES......Page 892
Glossary......Page 895
Glossary......Page 897
Top-down sampling......Page 898
Cuttings......Page 899
Glossary......Page 900
Backwards analysis......Page 901
Abstract framework and analysis......Page 902
Applications......Page 903
Dynamic randomized incremental......Page 904
Glossary......Page 905
Theorem 40.4.1......Page 906
Linearizing range spaces......Page 907
Glossary......Page 908
Examples......Page 909
Theorem 40.5.2......Page 910
Open problem......Page 911
Method of conditional probabilities......Page 912
Wise independent distributions......Page 913
Constraint-based probability spaces......Page 914
Applications......Page 915
Approximations......Page 916
Nets......Page 917
Open problems......Page 918
40.8 Optimal divide-and-conquer......Page 919
40.9 Optimization......Page 920
40.11 Probabilistic proof techniques......Page 921
Surveys......Page 922
References......Page 923
41.1 Numerical nonrobustness issues......Page 927
41.2 The nature of geometric computation......Page 928
What is a finite-precision line ?......Page 930
Topologically-consistent distortion......Page 932
Arithmetical approaches......Page 933
41.4 Exact approach......Page 934
Glossary......Page 935
Big expression packages......Page 936
Theory......Page 937
Constructive root bounds......Page 938
Filters......Page 939
Precision complexity......Page 940
Beyond algebraic......Page 941
Applications......Page 942
The basic issues......Page 943
Converting generic to general algorithms......Page 944
Applications and practice......Page 945
41.6 Open problems......Page 946
References......Page 947
Introduction......Page 953
Build-and-search......Page 954
2-Dimensional convex hulls......Page 955
Open problems......Page 956
Glossary......Page 957
Glossary......Page 958
Open problems......Page 959
Glossary......Page 960
42.6 Visibility, envelopes, and optimization......Page 961
Glossary......Page 962
Related chapters......Page 963
References......Page 964
What is parametric search ?......Page 968
Problem statement......Page 969
The decision-tree algorithm......Page 970
Improvements using parallelism......Page 971
Problem statement......Page 972
Evaluating f (0* )......Page 973
Further improvements......Page 974
Fixed-value evaluation......Page 975
Improvements using parallelism......Page 976
Choice of monotonic function......Page 977
Evaluating f (0*)......Page 978
43.6 Other results......Page 979
References......Page 980
Glossary......Page 982
Glossary......Page 983
Glossary......Page 986
Cuttings......Page 987
Simplex range searching......Page 988
Polyhedral algorithms......Page 989
Lower bounds for range searching......Page 991
References......Page 993
Glossary......Page 996
Glossary......Page 997
Glossary......Page 998
Megiddo's algorithms......Page 999
45.4 Ransomized algorithms......Page 1000
Clarkson's algorithm......Page 1001
45.5 Derandomized methods......Page 1002
45.6 LP-type problems......Page 1003
Glossary......Page 1004
Glossary......Page 1005
Glossary......Page 1007
References......Page 1008
Glossary......Page 1012
46.1.2 Algorithms......Page 1013
BFGS method for unconstrained minimization......Page 1014
Convergence......Page 1015
46.2.1 Optimality conditions......Page 1016
Method of central sections (mcs)......Page 1017
Method of inscribed ellipsoids (mie)......Page 1018
46.3.1 Duality......Page 1019
46.3.2 Algorithms......Page 1020
46.3.4 Interior-point methods......Page 1021
Glossary......Page 1022
A generic primal-dual interior-point method......Page 1023
Complexity of interior-point methods......Page 1024
46.4.1 OPTIMALITY CONDITIONS AND DUALITY......Page 1025
Branch-and-bound......Page 1026
Polyhedral combinatorics......Page 1027
46.5.1 Interior-point methods for nonlinear programming......Page 1028
Glossary......Page 1029
References......Page 1031
Glossary......Page 1034
Cell decomposition......Page 1036
47.1.2 Lower bounds......Page 1037
Glossary......Page 1038
A convex polygon......Page 1039
Voronoi diagrams......Page 1040
The general motion planning problem with two degrees of freedom......Page 1041
A convex polygon in a planar polygonal environment......Page 1042
A nonconvex polygon......Page 1043
A ball in a 3D polyhedral environment......Page 1044
The general motion planning problem with three degrees of freedom......Page 1045
Coordinated motion planning......Page 1046
47.3 Variants of the motion planning problem......Page 1047
Shortest paths......Page 1048
Practical approaches to motion planning......Page 1049
Exploratory motion planning......Page 1050
Nonholonomic motion planning......Page 1051
On-line motion planning......Page 1052
Implementation of complete solutions......Page 1053
47.4 Davenport-schinzel sequences......Page 1054
Related chapters......Page 1055
References......Page 1056
Glossary......Page 1062
Number of degrees of freedom of a linkage......Page 1063
Glossary......Page 1064
Synthesizing form / force closure grasps......Page 1065
48.2.3 Part feeding......Page 1066
Number of hands in assembly......Page 1068
Monotome two-handed assembly sequencing......Page 1069
Open problem......Page 1070
Complete algorithms......Page 1071
Probabilistic algorithms......Page 1072
Distance computation......Page 1073
Glossary......Page 1074
48.5.1 Manipulation planning......Page 1075
48.5.2 Nonholonomic robots......Page 1076
Planning for noncontrollable robots......Page 1077
One-step planning......Page 1078
Optimal-time control planning......Page 1079
Nondirectional data structures......Page 1080
Model building......Page 1081
Pursuit-evasion......Page 1082
Related chapters......Page 1083
References......Page 1084
Geometry vs. radiometry and psychophysics......Page 1091
Trading solution quality for computation time......Page 1092
49.2 Graphics as a computational process......Page 1093
Representation: geometry, light, and forces......Page 1094
Interaction (simulation of dynamics)......Page 1095
Geometry capture......Page 1096
Motion capture......Page 1097
Glossary......Page 1098
Local visibility comprtations......Page 1099
Conservative algorithms......Page 1100
Shading......Page 1101
Aliasing......Page 1102
Discrepancy......Page 1103
Computing the discrepancy......Page 1104
Open problems......Page 1105
Index and search......Page 1106
Interaction......Page 1107
Dynamics......Page 1108
Related chapters......Page 1109
References......Page 1110
50.3 Motion models......Page 1113
Glossary......Page 1114
Convex hull example......Page 1115
Glossary......Page 1116
Convex hull, revisited......Page 1117
Proximity problems......Page 1119
Triangulations and tilings......Page 1120
Collision detection......Page 1121
Connectivity and clustering......Page 1122
Open problems......Page 1124
Surveys......Page 1127
References......Page 1128
Glossary......Page 1131
Hierarchical clustering......Page 1132
K-means type clustering......Page 1133
Data mining......Page 1134
Hough transforms......Page 1135
Glossary......Page 1136
51.3 Polygonal approximation......Page 1138
Iterative endpoint fitting......Page 1139
Point pattern matching......Page 1140
Glossary......Page 1141
Symmetry detection......Page 1142
Glossary......Page 1143
Regular projections......Page 1144
Visualization......Page 1145
Perspective projections and intrinsic degeneracies......Page 1146
Glossary......Page 1148
Text-block isolation......Page 1149
Minimal-size training-set consistent subsets......Page 1150
Nearest-neighbor searching......Page 1151
Related chapters......Page 1152
References......Page 1153
Glossary......Page 1159
Glossary......Page 1160
Glossary......Page 1161
Bounds on the area......Page 1162
Bounds on the angular resolution......Page 1163
Tradeoff between area and aspect ratio......Page 1164
Tradeoff between area and angular resolution......Page 1165
52.3 Complexity of graph drawing problems......Page 1166
52.4 Example of a graph drawing algorithm......Page 1167
Physical simulation......Page 1171
Three-dimensional straight-line drawings......Page 1172
Graph drawing checkers......Page 1173
Incremental graph drawing......Page 1174
Fixed parameter tractability......Page 1175
52.7 Sources and related material......Page 1176
References......Page 1177
53.1 Tensor product surfaces......Page 1182
Glossary......Page 1183
Parametric bezier and b-splines......Page 1184
Coons patches and gordon surfaces......Page 1185
Multisided patches......Page 1186
S-patches......Page 1187
Multivariate box splines and simplex splines......Page 1188
Main results......Page 1189
A-splines......Page 1190
Simplex- and box-based schemes......Page 1191
Main algorithms......Page 1193
Hierarchical splines......Page 1194
Differential equations and surface splines......Page 1195
References......Page 1197
Glossary......Page 1204
Glossary......Page 1205
Cut, web, and spanning trees......Page 1206
Data structure and operators......Page 1207
Glossary......Page 1208
54.2.2 Prediction......Page 1209
54.3 Connectivity compression......Page 1210
54.3.1 Edgebreaker......Page 1211
Edgebreaker decompression......Page 1212
Guaranteed encoding of the clers string......Page 1214
Statistical encoding......Page 1215
Topological surgery and mpeg-4......Page 1216
Hardware decompression in java 3D......Page 1217
54.4 Surface simplification......Page 1218
54.4.1 Vertex clustering......Page 1219
54.4.2 Edge collapsing......Page 1221
54.4.3 Mixed aproaches......Page 1222
54.4.4 Error measures......Page 1223
Glossary......Page 1225
54.5.2 Normal meshes......Page 1226
54.5.4 Swingwrapper......Page 1227
54.6 Progressive transmission......Page 1228
54.6.2 Compressed progressive meshes......Page 1229
54.6.4 Kd-trees......Page 1230
Surveys......Page 1231
References......Page 1232
Glossary......Page 1236
Results......Page 1237
Open problems......Page 1240
Glossary......Page 1241
Results......Page 1242
55.3 numerically controlled machining......Page 1244
Results......Page 1245
Open problems......Page 1247
Related chapters......Page 1248
References......Page 1249
Glossary......Page 1252
Glossary......Page 1253
56.1.2 Boundary representation......Page 1254
Glossary......Page 1255
Glossary......Page 1257
56.1.6 Conversion between representations......Page 1258
Spatial relationships......Page 1259
Glossary......Page 1260
56.2.2 Algorithmic infrastructure......Page 1261
Glossary......Page 1264
56.3.2 Constraint-based design......Page 1265
56.3.3 Semantic problems......Page 1267
Features......Page 1268
Further reading......Page 1269
References......Page 1270
57.1 Multivariate ranking......Page 1274
Halfspace location depth......Page 1275
Other location depth notions......Page 1277
Regression depth......Page 1278
57.2 Computing depth......Page 1280
Bivariate algorithms......Page 1281
Algorithms in higher dimensions......Page 1282
57.3 Other statistical techniques......Page 1283
References......Page 1284
58.1 Spatial data structures......Page 1288
58.1.1 Raster and vector structures......Page 1289
58.2 Spatial analysis......Page 1290
58.2.1 Map overlay......Page 1291
58.2.3 Spatial interpolation......Page 1292
Glossary......Page 1293
58.3.1 Label placement......Page 1294
58.3.2 Cartographic generalization......Page 1295
58.3.3 Special-purpose maps......Page 1296
58.3.4 Dynamic and animated maps......Page 1298
58.4.1 Construction and simplification of dems......Page 1299
58.4.3 Derived maps and products......Page 1300
58.6 Open problems......Page 1301
Related chapters......Page 1303
References......Page 1304
Glossary......Page 1310
Properties of grassmann-cayley algebra......Page 1311
59.2 Geometry g.-c. algebra bracket algebra......Page 1312
Philosophy of invariant theory:......Page 1314
Multilinear cayley factorization......Page 1315
Glossary......Page 1316
59.4.2 Bar frameworks......Page 1318
59.4.3 Bar-and-body frameworks......Page 1319
Surveys......Page 1320
References......Page 1321
60.1 Rigidity of bar frameworks......Page 1322
Glossary......Page 1323
Basic connections......Page 1324
Glossary......Page 1325
Basic properties in all dimensions......Page 1326
Inductive constructions for isostatic graphs......Page 1327
Plane isostatic graphs......Page 1328
Algorithms for generic 2-rigidity......Page 1329
Open problems......Page 1330
Basic results......Page 1331
Other related structures......Page 1334
Basic connections......Page 1335
Glossary......Page 1337
Basic results......Page 1338
Basic results......Page 1340
Algorithms......Page 1341
Glossary......Page 1342
First-order rigidity......Page 1343
Angles in cad......Page 1344
Glossary......Page 1345
Basic results......Page 1346
Surveys and basic sources......Page 1347
References......Page 1348
Sphere packing in Rn......Page 1350
Glossary......Page 1351
Dimensions up to 24......Page 1352
Dimensions up to 2048......Page 1354
Packing in the unit sphere, or spherical codes......Page 1355
General bounds on sphere-packing density......Page 1358
Glossary......Page 1359
Glossary......Page 1360
Glossary......Page 1361
General bounds on code size for the hamming metric......Page 1362
Codes for exotic metrics......Page 1364
Construction B......Page 1365
Construction E......Page 1366
E8 and the leech lattice 24......Page 1367
Superballs......Page 1368
References......Page 1369
62.1 Periodic crystals......Page 1372
Main results......Page 1373
Delone's reformulation of the classical foundations......Page 1374
Glossary......Page 1375
62.1.3 Modeling x-ray diffraction......Page 1376
Main results......Page 1377
62.2.1 Point-set models......Page 1378
Glossary......Page 1379
Main results......Page 1380
Glossary......Page 1381
Main results......Page 1382
Glossary......Page 1383
62.2.3 Modelling crystal "growth"......Page 1384
Glossary......Page 1385
Surveys......Page 1386
References......Page 1387
Glossary......Page 1389
From sequence to function......Page 1390
Glossary......Page 1391
Space-filling diagrams......Page 1392
63.3 Meshing......Page 1393
Glossary......Page 1394
63.4 Connectivity and shape features......Page 1395
Glossary......Page 1396
Incremental algorithm......Page 1397
Glossary......Page 1398
Morse-smale complexes......Page 1399
Structure alignment......Page 1400
63.7 Measures and derivatives......Page 1401
Geometric inclusion-exclusion......Page 1402
Further reading......Page 1403
References......Page 1404
Introduction......Page 1407
General sources......Page 1408
Further technical remarks......Page 1409
Stand-alone software......Page 1410
Stand-alone software......Page 1411
Stand-alone software......Page 1412
Assitional web pages......Page 1415
Stand-alone software......Page 1416
64.2 Features of selected software systems......Page 1417
References......Page 1420
Degeneracy handling......Page 1426
Common roots and differences......Page 1427
65.1 LEDA......Page 1428
Correctness......Page 1429
65.1.1 The structure of leda......Page 1430
65.1.3 Data structures......Page 1431
65.1.5 Visualization (GeoWin)......Page 1432
65.1.6 Program examples......Page 1433
Upper convex hull......Page 1434
Delaunay flipping......Page 1435
65.2 CGAL......Page 1436
Flexibility......Page 1437
65.2.1 Geometric kernel......Page 1438
Example: orientation of triple......Page 1440
65.2.2 Basic library......Page 1441
Example of upper convex hull algoithm......Page 1442
Example of user kernel......Page 1444
Polygon and nef polygon......Page 1446
Triangulations, voronoi diagrams, and alpha shapes......Page 1447
Optimization......Page 1448
Related chapters......Page 1449
References......Page 1450