Handbook of Discrete and Computational Geometry

c3014_fm......Page 2
Handbook of Discrete and Computational Geometry, Second Edition......Page 7
Discrete Mathematics and ITS Applications......Page 4
PREFACE......Page 9
PREFACE TO THE SECOND EDITION......Page 11
CONTRIBUTORS......Page 15
CONTENTS......Page 13
GLOSSARY......Page 20
Contents......Page 0
SYLVESTER-TYPE RESULTS......Page 21
MIXED PROBLEMS......Page 23
1.2 METRIC PROBLEMS......Page 26
REPEATED DISTANCES......Page 27
DISTINCT DISTANCES......Page 29
RELATED RESULTS......Page 30
CONJECTURES OF ERDOS......Page 31
GLOSSARY......Page 32
FORBIDDEN DISTANCES......Page 33
OPEN PROBLEMS......Page 34
RELATED CHAPTERS......Page 35
REFERENCES......Page 36
GLOSSARY......Page 42
KNOWN VALUES OF PACKING AND COVERING DENSITIES......Page 44
THE KEPLER CONJECTURE......Page 46
EXISTENCE OF ECONOMICAL ARRANGEMENTS......Page 48
UPPER BOUNDS FOR Æ(Bd) AND LOWER BOUNDS FOR #(Bd)......Page 49
PACKING IN AND COVERING OF A BODY WITH GIVEN SHAPE......Page 50
SAUSAGE CONJECTURES......Page 53
GLOSSARY......Page 54
SPHERICAL SPACE......Page 57
HYPERBOLIC SPACE......Page 58
GLOSSARY......Page 61
2.6 SELECTED PROBLEMS ON LATTICE ARRANGEMENTS......Page 62
2.7 PACKING AND COVERING WITH SEQUENCES OF CONVEX BODIES......Page 63
REFERENCES......Page 65
GLOSSARY......Page 70
MAIN RESULTS......Page 72
GLOSSARY......Page 73
MAIN RESULTS......Page 75
OPEN PROBLEMS......Page 76
GLOSSARY......Page 77
GLOSSARY......Page 78
MAIN RESULTS......Page 81
3.4 NONPERIODIC AND APERIODIC TILINGS......Page 82
GLOSSARY......Page 83
MAIN RESULTS......Page 84
3.5 OTHER TILINGS......Page 85
RELATED CHAPTERS......Page 86
REFERENCES......Page 87
GLOSSARY......Page 90
4.1.1 GENERALIZATIONS TO NONCONVEX SETS......Page 91
4.1.2 INTERSECTIONS IN MORE THAN A POINT......Page 92
4.1.3 REDUCING d+1......Page 93
RESULTS......Page 95
4.1.6 RELATED THEOREMS......Page 96
4.1.7 RELATED ALGORITHMS......Page 97
GLOSSARY......Page 98
NOTATION......Page 99
4.2.1 HADWIGER'S TRANSVERSAL THEOREM......Page 100
GLOSSARY......Page 101
4.2.4 TRANSLATES......Page 102
4.2.6 SPACE OF TRANSVERSALS......Page 104
4.2.7 GEOMETRIC PERMUTATIONS......Page 105
4.2.9 CONVEXITY ON THE AFFINE GRASSMANNIAN......Page 107
4.2.10 OPEN PROBLEMS......Page 108
RELATED CHAPTERS......Page 109
REFERENCES......Page 110
GLOSSARY......Page 114
GLOSSARY......Page 117
ARRANGEMENTS OF STRAIGHT LINES......Page 118
CONFIGURATIONS OF POINTS......Page 120
ALLOWABLE SEQUENCES......Page 121
LOCAL SEQUENCES AND CLUSTERS OF STARS......Page 122
STRETCHABLE AND NONSTRETCHABLE ARRANGEMENTS......Page 123
GLOSSARY......Page 125
RELATIONS AMONG NUMBERS OF VERTICES, EDGES, AND FACES......Page 126
THE NUMBER OF CELLS OF DIFFERENT SIZES......Page 127
SIMPLICIAL ARRANGEMENTS......Page 129
COMPLEXITY OF SETS OF CELLS IN AN ARRANGEMENT......Page 130
GLOSSARY......Page 131
EMBEDDING IN LARGER STRUCTURES......Page 132
MOVING FROM ONE ARRANGEMENT TO ANOTHER......Page 133
THE NUMBER OF ARRANGEMENTS......Page 134
HOW MUCH SPACE IS NEEDED TO SPECIFY AN ARRANGEMENT?......Page 135
REALIZABILITY......Page 136
GLOSSARY......Page 137
APPLICATIONS OF DUALITY......Page 138
PSEUDOTRIANGULATIONS......Page 139
RELATED CHAPTERS......Page 140
REFERENCES......Page 141
GLOSSARY......Page 146
GLOSSARY......Page 148
GLOSSARY......Page 149
GLOSSARY......Page 150
6.2 AXIOMS AND REPRESENTATIONS......Page 151
GLOSSARY......Page 152
6.2.2 COCIRCUITS......Page 153
GLOSSARY......Page 154
GLOSSARY......Page 155
GLOSSARY......Page 156
6.2.6 AN EXAMPLE......Page 157
GLOSSARY......Page 159
GLOSSARY......Page 160
CONSEQUENCES OF THE UNIVERSALITY THEOREM......Page 161
TRIANGLES IN ARRANGEMENTS OF PSEUDOLINES......Page 162
SIMPLICIAL CELLS IN PSEUDOARRANGEMENTS......Page 163
6.3.4 MATROID POLYTOPES......Page 164
ALGORITHMIC APPROACH TO POLYTOPE CLASSIFICATION......Page 165
RELATED CHAPTERS......Page 166
REFERENCES......Page 167
GLOSSARY......Page 169
V-POLYTOPES WITH MANY VERTICES......Page 170
CONVEX HULL OF INTEGRAL POINTS......Page 171
FLATNESS THEOREMS......Page 172
MINKOWSKI'S CONVEX BODY THEOREM......Page 173
7.3 COUNTING PROBLEM......Page 174
SOME EXPLICIT FORMULAS IN LOW DIMENSIONS......Page 175
EXPONENTIAL SUMS OVER RATIONAL POLYHEDRA......Page 176
THE IDEA OF THE ALGORITHM......Page 178
CONNECTIONS WITH TORIC VARIETIES......Page 179
CONNECTIONS WITH VALUATIONS......Page 180
ANALYTICAL METHODS......Page 181
PROBABILISTIC METHODS......Page 182
GLOSSARY......Page 183
GENERAL PROPERTIES......Page 184
EULER-MACLAURIN FORMULAS......Page 185
THE h -VECTOR......Page 186
INTEGRAL POINTS IN RATIONAL POLYTOPES......Page 187
PROBLEM WITH QUANTIFIERS......Page 188
REFERENCES......Page 189
INTRODUCTION......Page 193
8.1.1 THE EUCLIDEAN SPACES Ld 2......Page 194
GLOSSARY......Page 195
8.1.3 THE OTHER p......Page 196
8.2.2 THE DIMENSION OF EMBEDDINGS IN L......Page 197
8.2.3 THE JOHNSON-LINDENSTRAUSS LEMMA: FLATTENING IN L2......Page 198
GLOSSARY......Page 199
PLANAR-GRAPH METRICS AND OTHER CLASSES WITH A FORBIDDEN MINOR......Page 200
EARTH-MOVER DISTANCE (EMD)......Page 201
GLOSSARY......Page 202
8.4.1 PROBABILISTIC EMBEDDINGS IN TREES......Page 203
8.4.2 RAMSEY-TYPE THEOREMS......Page 204
8.5 ALGORITHMIC APPLICATIONS OF EMBEDDINGS......Page 205
REFERENCES......Page 209
GLOSSARY......Page 213
CONNECTIVITY......Page 215
9.3 CONFIGURATION SPACES WITHOUT SELF-INTER- SECTIONS......Page 216
WHICH LINKAGES ARE LOCKED?......Page 217
UNLOCKED LINKAGES......Page 218
SPECIAL CLASSES OF LINKAGES......Page 220
FLIPS AND FLIPTURNS......Page 221
TRACING CURVES......Page 222
ARBITRARY CONFIGURATION SPACES......Page 223
HARDNESS RESULTS......Page 224
ALGORITHMS......Page 225
FOUR-BAR MECHANISM......Page 226
FURTHER READING......Page 227
APPLICATIONS IN BIOLOGY......Page 228
REFERENCES......Page 230
GLOSSARY......Page 235
CROSSING-FREE GEOMETRIC GRAPHS......Page 236
TURAN-TYPE PROBLEMS......Page 237
RAMSEY-TYPE PROBLEMS......Page 239
OPEN PROBLEMS......Page 240
GLOSSARY......Page 241
GENERAL ESTIMATES......Page 242
OPEN PROBLEMS......Page 244
10.3 GENERALIZATIONS......Page 245
TOPOLOGICAL GRAPHS......Page 246
GEOMETRIC HYPERGRAPHS......Page 247
SURVEYS......Page 249
REFERENCES......Page 250
11.1 r-RAMSEY SETS......Page 255
GLOSSARY......Page 258
GLOSSARY......Page 260
11.4 EDGE-RAMSEY SETS......Page 261
11.5 HOMOTHETIC RAMSEY SETS AND DENSITYTHEOREMS......Page 262
GLOSSARY......Page 264
ASYMMETRIC RAMSEY THEOREMS......Page 265
PARTITIONS WITH INFINITELY MANY PARTS......Page 266
COMPLEXITY ISSUES......Page 267
REFERENCES......Page 268
GLOSSARY......Page 271
12.1.2 NATURAL DISTRIBUTIONS......Page 272
12.1.3 UNIFORM RANDOM POINTS IN CONVEX BODIES......Page 273
OPEN PROBLEMS......Page 278
OPEN PROBLEM......Page 279
12.1.5 CONVEX HULLS FOR OTHER DISTRIBUTIONS......Page 280
12.2.1 GEOMETRIC CONFIGURATIONS......Page 281
GLOSSARY......Page 282
12.3.1 RANDOM HYPERPLANES AND HALFSPACES......Page 283
12.3.2 RANDOM FLATS THROUGH CONVEX BODIES......Page 284
12.4 RANDOM CONGRUENT COPIES......Page 285
12.5.1 GENERAL MOSAICS......Page 286
12.5.2 HYPERPLANE TESSELLATIONS......Page 287
SOURCES FOR STOCHASTIC GEOMETRY IN GENERAL......Page 288
RELEVANT SURVEYS AND FURTHER SOURCES......Page 289
REFERENCES......Page 290
GLOSSARY......Page 295
PROBABILITY MEASURES AND DISCREPANCY......Page 298
13.3 ALIGNED RECTANGLES IN THE UNIT SQUARE......Page 299
13.4 ALIGNED BOXES IN A UNIT k-CUBE......Page 301
13.5 MOTION-INVARIANT PROBLEMS......Page 304
GLOSSARY......Page 305
13.8 WORK OF MONTGOMERY......Page 307
GLOSSARY......Page 308
13.10 BOUNDARIES OF GENERATORS FORHOMOTHETICALLY INVARIANT J......Page 310
GLOSSARY......Page 311
13.11 D(K,J,2,N) IN LIGHT OF DISTANCE GEOMETRY......Page 312
GLOSSARY......Page 314
REFERENCES......Page 316
WHERE HAS TOPOLOGY BEEN APPLIED IN COMPUTER SCIENCE?......Page 321
GLOSSARY......Page 322
14.2.1 THE HAM SANDWICH THEOREM......Page 325
TOPOLOGICAL BACKGROUND......Page 326
TOPOLOGICAL BACKGROUND......Page 327
TOPOLOGICAL BACKGROUND......Page 328
APPLICATIONS AND RELATED RESULTS......Page 329
14.2.5 RADIAL PARTITIONS BY POLYHEDRAL FANS......Page 330
14.2.7 PARTITIONS BY CONVEX SETS......Page 331
14.2.9 OTHER EQUIPARTITIONS......Page 332
14.3.1 BORSUK'S PROBLEM......Page 333
14.3.2 KNASTER'S PROBLEM......Page 334
GLOSSARY......Page 335
APPLICATIONS AND RELATED RESULTS......Page 336
14.4.2 COLORED TVERBERG THEOREMS......Page 337
OTHER RELATED RESULTS......Page 339
GLOSSARY......Page 340
FURTHER READING......Page 341
REFERENCES......Page 342
GLOSSARY......Page 346
GLOSSARY......Page 347
15.3 HOW MANY n-OMINOES ARE THERE?......Page 349
UNSOLVED PROBLEMS......Page 350
GLOSSARY......Page 351
COMPOSITIONS AND ROW-CONVEX POLYOMINOES......Page 353
ROW-COLUMN-CONVEX POLYOMINOES......Page 354
WIDTH-k POLYOMINOES......Page 355
DIRECTED POLYOMINOES......Page 356
GLOSSARY......Page 357
15.7 RECTANGLES OF POLYOMINOES......Page 360
REFERENCES......Page 366
GLOSSARY......Page 368
GLOSSARY......Page 371
GLOSSARY......Page 373
GLOSSARY......Page 374
GLOSSARY......Page 376
ZONOTOPES......Page 377
CYCLIC POLYTOPESCyclic polytopes can......Page 378
OPEN PROBLEMS......Page 379
GLOSSARY......Page 380
OPEN PROBLEMS......Page 381
GLOSSARY......Page 382
GLOSSARY......Page 384
16.2 METRIC PROPERTIES......Page 385
GLOSSARY......Page 386
GLOSSARY......Page 387
GLOSSARY......Page 389
SOME COMPUTATIONS......Page 391
AN APPLICATION......Page 392
REFERENCES......Page 393
GLOSSARY......Page 396
GLOSSARY......Page 397
MAIN RESULTS......Page 398
EXAMPLES......Page 399
MAIN RESULTS......Page 400
17.3.1 TRIANGULATING REGIONS BETWEEN POLYTOPES......Page 402
GLOSSARY......Page 403
MAIN RESULTS......Page 404
EXAMPLES......Page 405
MAIN RESULTS......Page 406
MAIN RESULTS......Page 407
MAIN RESULTS......Page 408
GLOSSARY......Page 409
MAIN RESULTS......Page 410
EXAMPLES......Page 411
17.5.4 COMPLETE BARYCENTRIC SUBDIVISIONS......Page 412
GLOSSARY......Page 413
MAIN RESULTS......Page 414
17.6.1 FIBER POLYTOPES......Page 415
FURTHER READING......Page 416
REFERENCES......Page 417
GLOSSARY......Page 420
THE KRUSKAL-KATONA THEOREM AND SOME RELATIVES......Page 421
MULTICOMPLEXES AND MACAULAY'S THEOREM......Page 422
GLOSSARY......Page 423
COHEN-MACAULAY COMPLEXES......Page 424
LERAY COMPLEXES......Page 425
GLOSSARY......Page 426
PSEUDOMANIFOLDS......Page 427
POLYTOPES AND SPHERES......Page 428
COMMENTS......Page 429
BASIC f -VECTOR RELATIONS......Page 430
COMMENTS......Page 431
GLOSSARY......Page 432
LINEAR INEQUALITIES......Page 433
HYPERPLANE ARRANGEMENTS AND ZONOTOPES......Page 435
GENERAL 3- AND 4-POLYTOPES......Page 436
COMMENTS......Page 437
18.6 OPEN PROBLEMS......Page 438
REFERENCES......Page 440
GLOSSARY......Page 444
ENUMERATION AND CONSTRUCTION......Page 446
SYMMETRY GROUPS......Page 447
GLOSSARY......Page 448
ENUMERATION AND CONSTRUCTION......Page 449
GLOSSARY......Page 450
ENUMERATION......Page 451
19.4 THE GRUNBAUM-DRESS POLYHEDRA......Page 452
ENUMERATION......Page 453
GLOSSARY......Page 454
19.6 REFLECTION GROUPS......Page 455
GENERAL PROPERTIES......Page 456
ENUMERATION AND GROUPS......Page 458
GLOSSARY......Page 460
GENERAL PROPERTIES......Page 461
CLASSIFICATION BY TOPOLOGICAL TYPE......Page 462
REALIZATIONS......Page 463
SURVEYS......Page 464
REFERENCES......Page 465
GLOSSARY......Page 468
GLOSSARY......Page 470
SUBGRAPHS AND INDUCED SUBGRAPHS......Page 471
CONNECTIVITY AND SEPARATION......Page 472
EXPANSION......Page 473
GLOSSARY......Page 474
20.4 POLYTOPAL DIGRAPHS......Page 476
GLOSSARY......Page 477
SHELLABILITY AND COLLAPSIBILITY......Page 478
FACET-FORMING POLYTOPES AND SMALL LOW-DIMENSIONAL FACES......Page 479
RECONSTRUCTION......Page 481
EMPTY FACES AND POLYTOPES WITH FEW VERTICES......Page 483
RELATED CHAPTERS......Page 484
REFERENCES......Page 485
GLOSSARY......Page 490
BASIC RESULTS......Page 492
BASIC RESULTS......Page 494
EBERHARD-TYPE RESULTS......Page 497
GENERAL RESULTS......Page 499
GENERAL RESULTS......Page 500
RELATED CHAPTERS......Page 502
REFERENCES......Page 503
GLOSSARY......Page 505
POLARITY......Page 506
GLOSSARY......Page 507
THE SIZES OF COMBINATORIAL DESCRIPTIONS......Page 508
MAIN RESULTS AND OPEN PROBLEMS......Page 510
22.3.1 THE INCREMENTAL METHOD......Page 511
22.3.2 THE GRAPH TRAVERSAL METHOD......Page 513
THE GENERAL CASE......Page 514
THE PRIMAL-DUAL METHOD......Page 515
THE 2-DIMENSIONAL CASE......Page 516
22.5 RELATED TOPICS......Page 517
REFERENCES......Page 519
GLOSSARY......Page 523
RELATION TO CONVEXITY......Page 525
23.2 BASIC ALGORITHMS......Page 526
THE RANDOMIZED INCREMENTAL ALGORITHM......Page 527
OTHER ALGORITHMS......Page 528
HIGHER-ORDER VORONOI DIAGRAMS......Page 529
CONFORMING DELAUNAY TRIANGULATIONS......Page 530
OTHER DISTANCE MEASURES......Page 531
KINETIC VORONOI DIAGRAMS......Page 532
IMPLEMENTATIONS......Page 533
VISIBILITY DEPTH ORDERING......Page 534
FURTHER READING......Page 535
REFERENCES......Page 536
GLOSSARY......Page 539
COUNTING CELLS......Page 540
PLANAR ARRANGEMENTS......Page 541
THREE AND HIGHER DIMENSIONS......Page 542
GLOSSARY......Page 543
COMBINATORIAL COMPLEXITY BOUNDS FOR SUBSTRUCTURES......Page 545
UNION BOUNDARY......Page 546
ADDITIONAL COMBINATORIAL BOUNDS......Page 547
24.3 REPRESENTATIONS AND DECOMPOSITIONS......Page 548
SKELETON......Page 549
BOTTOM VERTEX DECOMPOSITION OF HYPERPLANE ARRANGEMENTS......Page 550
VERTICAL DECOMPOSITION......Page 551
24.4 ALGORITHMS FOR ARRANGEMENTS......Page 552
24.4.1 DETERMINISTIC ALGORITHMS......Page 553
24.4.2 RANDOMIZED ALGORITHMS......Page 555
LOWER ENVELOPE......Page 556
MANY CELLS......Page 557
ARRANGEMENTS OF CONVEX POLYTOPES......Page 558
EXAMPLE: MINIMUM AREA TRIANGLE......Page 559
OTHER APPLICATIONS......Page 560
EXACT COMPUTING......Page 561
APPROXIMATE ARITHMETIC IN PREDICATE EVALUATION......Page 562
OPEN PROBLEM......Page 563
2D ARRANGEMENTS IN CGAL......Page 564
RELATED CHAPTERS......Page 565
REFERENCES......Page 566
GLOSSARY......Page 573
ALGORITHMS......Page 574
OPTIMALITY PROPERTIES......Page 575
SIMPLE POLYGONS......Page 576
PLANAR STRAIGHT-LINE GRAPHS......Page 577
25.3 OPTIMAL TRIANGULATIONS......Page 578
EDGE FLIPPING AND EDGE INSERTION......Page 579
MINIMUM WEIGHT TRIANGULATION......Page 580
NO SMALL ANGLES......Page 581
NO LARGE ANGLES......Page 582
SURFACE MESHES......Page 583
GLOSSARY......Page 584
GENERAL POLYHEDRA......Page 585
THREE-DIMENSIONAL MESH GENERATION......Page 586
GLOSSARY......Page 587
POLYTOPES......Page 588
RELATED CHAPTERS......Page 589
REFERENCES......Page 590
GLOSSARY......Page 593
POLYGON TYPES......Page 594
GLOSSARY......Page 595
TRIANGULATION......Page 596
COVERS AND PARTITIONS......Page 597
ORTHOGONAL POLYGONS......Page 598
AREA BISECTION......Page 599
DISSECTIONS......Page 600
26.3 POLYGON INTERSECTION......Page 601
EUCLIDEAN MEASURE......Page 602
LINK MEASURE......Page 604
VISIBILITY AND RAY SHOOTING......Page 605
CONTAINMENT OF POLYGONS......Page 606
INSCRIBING/CIRCUMSCRIBING POLYGONS......Page 607
POLYGON MORPHING......Page 608
CSG REPRESENTATION......Page 609
THREE-DIMENSIONAL POLYGONS......Page 610
REFERENCES......Page 611
INTRODUCTION......Page 617
GLOSSARY......Page 618
27.1 PATHS IN A SIMPLE POLYGON......Page 619
TWO-POINT QUERIES......Page 620
OPEN PROBLEMS......Page 621
CONTINUOUS DIJKSTRA METHOD......Page 622
TWO-POINT QUERIES......Page 623
OTHER RESULTS......Page 624
GLOSSARY......Page 625
LINK DISTANCE......Page 626
L1 METRIC......Page 627
WEIGHTED REGION METRIC......Page 628
MINIMUM-TIME PATHS......Page 629
OPTIMAL ROBOT MOTION......Page 630
OPEN PROBLEMS......Page 631
GLOSSARY......Page 632
TRAVELING SALESMAN PROBLEM......Page 633
WATCHMAN ROUTE PROBLEM......Page 634
GLOSSARY......Page 635
SPECIAL CASES......Page 636
APPROXIMATION ALGORITHMS......Page 637
OTHER METRICS......Page 638
GLOSSARY......Page 639
t-SPANNERS......Page 641
PLANAR t-SPANNERS......Page 642
SURVEYS......Page 643
REFERENCES......Page 644
GLOSSARY......Page 652
COVERS AND PARTITIONS......Page 653
28.1.1 FLOODLIGHT ILLUMINATION......Page 654
MAIN RESULTS......Page 655
GOALS......Page 656
VERTEX VISIBILITY GRAPHS......Page 657
OPEN PROBLEMS......Page 658
VISIBILITY POLYGON ALGORITHM......Page 659
ENDPOINT VISIBILITY GRAPH......Page 660
MAIN RESULTS......Page 661
GLOSSARY......Page 662
28.8.2 BINARY SPACE PARTITION TREES......Page 663
ALGORITHMS......Page 665
28.9 PENETRATING ILLUMINATION OF CONVEX BODIES......Page 666
GLOSSARY......Page 667
REFERENCES......Page 668
29.1 STATIC RECONSTRUCTION PROBLEMS......Page 673
GLOSSARY......Page 674
GLOSSARY......Page 676
MAIN RESULTS......Page 677
COMPUTER VISION......Page 679
TOMOGRAPHY AND SURFACES FROM CROSS-SECTIONS AND PROJECTIONS......Page 680
SURVEYS......Page 681
REFERENCES......Page 682
GLOSSARY......Page 685
GLOSSARY......Page 686
NONUNIFORM SAMPLE......Page 687
NONSMOOTHNESS, BOUNDARIES......Page 688
30.2 SURFACE RECONSTRUCTION......Page 689
GLOSSARY......Page 690
CRUST......Page 691
COCONE......Page 692
NATURAL NEIGHBOR......Page 693
WATERTIGHT SURFACES......Page 694
OPEN PROBLEMS......Page 695
GLOSSARY......Page 696
MAIN RESULTS......Page 697
REFERENCES......Page 698
INTRODUCTION......Page 701
REFERENCES......Page 702
GLOSSARY......Page 703
31.1.1 CONVERSION OF ONE PRESENTATION INTO THE OTHER......Page 704
RELATED CHAPTERS......Page 705
GLOSSARY......Page 706
FURTHER READING......Page 707
GLOSSARY......Page 708
31.3.1 CLASSICAL BACKGROUND, CHARACTERIZATIONS......Page 709
31.3.2 SOME VOLUME FORMULAS......Page 710
31.3.3 TRACTABILITY RESULTS......Page 711
31.3.6 RANDOMIZED ALGORITHMS......Page 712
RELATED CHAPTERS......Page 713
GLOSSARY......Page 714
31.4.3 INTRACTABILITY RESULTS......Page 715
31.4.4 RANDOMIZED ALGORITHMS......Page 716
REFERENCES......Page 717
31.5.2 OPTIMAL CONTAINMENT UNDER HOMOTHETY......Page 718
31.5.3 OPTIMAL CONTAINMENT UNDER AFFINITY: SIMPLICES......Page 719
31.5.4 OPTIMAL CONTAINMENT UNDER AFFINITY: ELLIPSOIDS......Page 720
REFERENCES......Page 721
APPLICATIONS......Page 722
REFERENCES......Page 723
GLOSSARY......Page 724
TRACTABILITY RESULTS......Page 725
REFERENCES......Page 726
GLOSSARY......Page 727
BASIC TOPOLOGICAL PROBLEMS AND APPLICATIONS......Page 728
GLOSSARY......Page 729
BASIC PROPERTIES......Page 731
OPEN PROBLEMS......Page 732
EXAMPLES AND ELEMENTARY PROPERTIES......Page 733
32.4 ALGEBRAIC TOPOLOGY......Page 734
GLOSSARY......Page 735
32.4.2 HOMOTOPY GROUPS......Page 736
EXAMPLES......Page 737
ALGORITHMS AND COMPLEXITY......Page 738
BASIC RESULTS......Page 739
MAIN RESULTS......Page 740
ALGORITHMS AND COMPLEXITY......Page 741
BASIC RESULTS......Page 742
GLOSSARY......Page 743
EXAMPLES......Page 745
BASIC RESULTS......Page 746
FURTHER READING......Page 747
REFERENCES......Page 748
33.1 FIRST-ORDER THEORY OF REALS......Page 751
GLOSSARY......Page 752
QUANTIFIER ELIMINATION PROBLEM......Page 753
TARSKI-SEIDENBERG THEOREM......Page 755
GLOSSARY......Page 756
33.3 REAL ALGEBRAIC NUMBERS......Page 757
GLOSSARY......Page 758
STURM-SYLVESTER THEOREM......Page 759
GLOSSARY......Page 760
33.4 UNIVARIATE DECOMPOSITION......Page 761
GLOSSARY......Page 762
CONSTRUCTING SAMPLE POINTS......Page 763
COLLINS'S APPROACH......Page 764
NEW APPROACHES USING CRITICAL POINTS......Page 765
33.7 APPLICATIONS......Page 766
OFFSET SURFACE CONSTRUCTION IN SOLID MODELING......Page 767
CONNECTION TO SEMIDEFINITE PROGRAMMING......Page 768
SURVEYS......Page 769
REFERENCES......Page 770
GLOSSARY......Page 773
LIST SEARCH AS ONE-DIMENSIONAL POINT LOCATION......Page 774
GLOSSARY......Page 775
SLABS AND PERSISTENCE......Page 776
TRAPEZOID GRAPH METHODS......Page 778
TRIANGULATIONS......Page 780
GLOSSARY......Page 781
DYNAMIC INTERVAL TREE......Page 782
OPEN PROBLEMS......Page 783
SUBDIVISION WALKING......Page 784
THREE-DIMENSIONAL POINT LOCATION......Page 785
OPEN PROBLEMS......Page 786
IMPLICIT POINT LOCATION......Page 787
REFERENCES......Page 788
PROBLEM CLASSIFICATION......Page 792
MINKOWSKI SUMS AND CONVEX OPTIMIZATION......Page 795
TRACKING CLOSEST FEATURES USING GEOMETRIC LOCALITY AND MOTION COHERENCE......Page 796
35.2 GENERAL POLYGONAL MODELS......Page 797
SEPARATION-DISTANCE COMPUTATION......Page 798
QUERIES ON BOUNDING VOLUMES......Page 799
35.3 PENETRATION-DEPTH COMPUTATION......Page 800
CONVEX POLYTOPES......Page 801
35.4 SPLINE AND ALGEBRAIC OBJECTS......Page 802
35.5 DYNAMIC QUERIES......Page 803
35.6 LARGE ENVIRONMENTS......Page 804
35.7 PROXIMITY QUERY PACKAGES......Page 806
RELATED CHAPTERS......Page 807
REFERENCES......Page 808
INTRODUCTION......Page 813
36.1 MODELS OF COMPUTATION......Page 814
36.2 ORTHOGONAL RANGE SEARCHING......Page 817
UPPER BOUNDS......Page 818
LOWER BOUNDS......Page 819
SECONDARY MEMORY STRUCTURES......Page 820
LINEAR-SIZE DATA STRUCTURES......Page 821
36.3 SIMPLEX RANGE SEARCHING......Page 823
LINEAR-SIZE DATA STRUCTURES......Page 824
DATA STRUCTURES WITH LOGARITHMIC QUERY TIME......Page 825
LOWER BOUNDS......Page 826
OPEN PROBLEMS......Page 827
MULTI-LEVEL STRUCTURES......Page 828
SEMIALGEBRAIC RANGE SEARCHING......Page 829
KINETIC RANGE SEARCHING......Page 830
OPEN PROBLEMS......Page 831
POINT INTERSECTION SEARCHING......Page 832
SEGMENT INTERSECTION SEARCHING......Page 833
RAY-SHOOTING QUERIES......Page 834
RELATED READING......Page 836
REFERENCES......Page 837
INTRODUCTION......Page 842
GLOSSARY......Page 843
GLOSSARY......Page 845
GLOSSARY......Page 846
GLOSSARY......Page 848
GLOSSARY......Page 849
OFF-LINE RAY SHOOTING IN AN ARBITRARY DIRECTION......Page 850
EXTENSIONS AND ALTERNATIVE METHODS......Page 851
ARBITRARY MOTIONS......Page 852
GLOSSARY......Page 853
GLOSSARY......Page 854
REFERENCES......Page 856
GLOSSARY......Page 860
GLOSSARY......Page 861
INTERSECTION DETECTION OF CONVEX POLYGONS......Page 862
SIMPLE POLYGONS......Page 863
INTERSECTION DETECTION WITH PREPROCESSING......Page 864
INTERSECTION DETECTION ALGORITHM......Page 865
GLOSSARY......Page 866
REPORTING LINE SEGMENT INTERSECTIONS......Page 867
RED-BLUE INTERSECTION PROBLEMS......Page 868
COUNTING LINE SEGMENT INTERSECTIONS......Page 869
INTERSECTION SEARCHING AND RANGE SEARCHING......Page 870
CONVEX POLYGONS......Page 871
SIMPLE POLYGONS AND CLIPPING......Page 872
INTERSECTION CONSTRUCTION IN HIGHER DIMENSIONS......Page 873
GRIDS......Page 874
38.6 SOURCES......Page 875
REFERENCES......Page 876
INTRODUCTION......Page 880
GLOSSARY......Page 881
RANDOM PROJECTION APPROACH......Page 882
DIVIDE-AND-CONQUER APPROACH......Page 884
AVERAGE-CASE ALGORITHMS......Page 885
GLOSSARY......Page 886
39.3 LOWER BOUNDS......Page 889
GLOSSARY......Page 890
REDUCTIONS......Page 891
39.4 LOW VS. HIGH DIMENSIONS IN COMPUTATIONAL GEOMETRY......Page 892
REFERENCES......Page 893
Glossary......Page 896
Glossary......Page 898
Top-down sampling......Page 899
Cuttings......Page 900
Glossary......Page 901
Backwards analysis......Page 902
Abstract framework and analysis......Page 903
Applications......Page 904
Dynamic randomized incremental......Page 905
Glossary......Page 906
Theorem 40.4.1......Page 907
Linearizing range spaces......Page 908
Glossary......Page 909
Examples......Page 910
Theorem 40.5.2......Page 911
Open problem......Page 912
Method of conditional probabilities......Page 913
Wise independent distributions......Page 914
Constraint-based probability spaces......Page 915
Applications......Page 916
Approximations......Page 917
Nets......Page 918
Open problems......Page 919
40.8 Optimal divide-and-conquer......Page 920
40.9 Optimization......Page 921
40.11 Probabilistic proof techniques......Page 922
Surveys......Page 923
References......Page 924
41.1 Numerical nonrobustness issues......Page 928
41.2 The nature of geometric computation......Page 929
What is a finite-precision line ?......Page 931
Topologically-consistent distortion......Page 933
Arithmetical approaches......Page 934
41.4 Exact approach......Page 935
Glossary......Page 936
Big expression packages......Page 937
Theory......Page 938
Constructive root bounds......Page 939
Filters......Page 940
Precision complexity......Page 941
Beyond algebraic......Page 942
Applications......Page 943
The basic issues......Page 944
Converting generic to general algorithms......Page 945
Applications and practice......Page 946
41.6 Open problems......Page 947
References......Page 948
Introduction......Page 954
Build-and-search......Page 955
2-Dimensional convex hulls......Page 956
Open problems......Page 957
Glossary......Page 958
Glossary......Page 959
Open problems......Page 960
Glossary......Page 961
42.6 Visibility, envelopes, and optimization......Page 962
Glossary......Page 963
Related chapters......Page 964
References......Page 965
What is parametric search ?......Page 969
Problem statement......Page 970
The decision-tree algorithm......Page 971
Improvements using parallelism......Page 972
Problem statement......Page 973
Evaluating f (0* )......Page 974
Further improvements......Page 975
Fixed-value evaluation......Page 976
Improvements using parallelism......Page 977
Choice of monotonic function......Page 978
Evaluating f (0*)......Page 979
43.6 Other results......Page 980
References......Page 981
Glossary......Page 983
Glossary......Page 984
Glossary......Page 987
Cuttings......Page 988
Simplex range searching......Page 989
Polyhedral algorithms......Page 990
Lower bounds for range searching......Page 992
References......Page 994
Glossary......Page 997
Glossary......Page 998
Glossary......Page 999
Megiddo's algorithms......Page 1000
45.4 Ransomized algorithms......Page 1001
Clarkson's algorithm......Page 1002
45.5 Derandomized methods......Page 1003
45.6 LP-type problems......Page 1004
Glossary......Page 1005
Glossary......Page 1006
Glossary......Page 1008
References......Page 1009
Glossary......Page 1013
46.1.2 Algorithms......Page 1014
BFGS method for unconstrained minimization......Page 1015
Convergence......Page 1016
46.2.1 Optimality conditions......Page 1017
Method of central sections (mcs)......Page 1018
Method of inscribed ellipsoids (mie)......Page 1019
46.3.1 Duality......Page 1020
46.3.2 Algorithms......Page 1021
46.3.4 Interior-point methods......Page 1022
Glossary......Page 1023
A generic primal-dual interior-point method......Page 1024
Complexity of interior-point methods......Page 1025
46.4.1 OPTIMALITY CONDITIONS AND DUALITY......Page 1026
Branch-and-bound......Page 1027
Polyhedral combinatorics......Page 1028
46.5.1 Interior-point methods for nonlinear programming......Page 1029
Glossary......Page 1030
References......Page 1032
Glossary......Page 1035
Cell decomposition......Page 1037
47.1.2 Lower bounds......Page 1038
Glossary......Page 1039
A convex polygon......Page 1040
Voronoi diagrams......Page 1041
The general motion planning problem with two degrees of freedom......Page 1042
A convex polygon in a planar polygonal environment......Page 1043
A nonconvex polygon......Page 1044
A ball in a 3D polyhedral environment......Page 1045
The general motion planning problem with three degrees of freedom......Page 1046
Coordinated motion planning......Page 1047
47.3 Variants of the motion planning problem......Page 1048
Shortest paths......Page 1049
Practical approaches to motion planning......Page 1050
Exploratory motion planning......Page 1051
Nonholonomic motion planning......Page 1052
On-line motion planning......Page 1053
Implementation of complete solutions......Page 1054
47.4 Davenport-schinzel sequences......Page 1055
Related chapters......Page 1056
References......Page 1057
Glossary......Page 1063
Number of degrees of freedom of a linkage......Page 1064
Glossary......Page 1065
Synthesizing form / force closure grasps......Page 1066
48.2.3 Part feeding......Page 1067
Number of hands in assembly......Page 1069
Monotome two-handed assembly sequencing......Page 1070
Open problem......Page 1071
Complete algorithms......Page 1072
Probabilistic algorithms......Page 1073
Distance computation......Page 1074
Glossary......Page 1075
48.5.1 Manipulation planning......Page 1076
48.5.2 Nonholonomic robots......Page 1077
Planning for noncontrollable robots......Page 1078
One-step planning......Page 1079
Optimal-time control planning......Page 1080
Nondirectional data structures......Page 1081
Model building......Page 1082
Pursuit-evasion......Page 1083
Related chapters......Page 1084
References......Page 1085
Geometry vs. radiometry and psychophysics......Page 1092
Trading solution quality for computation time......Page 1093
49.2 Graphics as a computational process......Page 1094
Representation: geometry, light, and forces......Page 1095
Interaction (simulation of dynamics)......Page 1096
Geometry capture......Page 1097
Motion capture......Page 1098
Glossary......Page 1099
Local visibility comprtations......Page 1100
Conservative algorithms......Page 1101
Shading......Page 1102
Aliasing......Page 1103
Discrepancy......Page 1104
Computing the discrepancy......Page 1105
Open problems......Page 1106
Index and search......Page 1107
Interaction......Page 1108
Dynamics......Page 1109
Related chapters......Page 1110
References......Page 1111
50.3 Motion models......Page 1114
Glossary......Page 1115
Convex hull example......Page 1116
Glossary......Page 1117
Convex hull, revisited......Page 1118
Proximity problems......Page 1120
Triangulations and tilings......Page 1121
Collision detection......Page 1122
Connectivity and clustering......Page 1123
Open problems......Page 1125
Surveys......Page 1128
References......Page 1129
Glossary......Page 1132
Hierarchical clustering......Page 1133
K-means type clustering......Page 1134
Data mining......Page 1135
Hough transforms......Page 1136
Glossary......Page 1137
51.3 Polygonal approximation......Page 1139
Iterative endpoint fitting......Page 1140
Point pattern matching......Page 1141
Glossary......Page 1142
Symmetry detection......Page 1143
Glossary......Page 1144
Regular projections......Page 1145
Visualization......Page 1146
Perspective projections and intrinsic degeneracies......Page 1147
Glossary......Page 1149
Text-block isolation......Page 1150
Minimal-size training-set consistent subsets......Page 1151
Nearest-neighbor searching......Page 1152
Related chapters......Page 1153
References......Page 1154
Glossary......Page 1160
Glossary......Page 1161
Glossary......Page 1162
Bounds on the area......Page 1163
Bounds on the angular resolution......Page 1164
Tradeoff between area and aspect ratio......Page 1165
Tradeoff between area and angular resolution......Page 1166
52.3 Complexity of graph drawing problems......Page 1167
52.4 Example of a graph drawing algorithm......Page 1168
Physical simulation......Page 1172
Three-dimensional straight-line drawings......Page 1173
Graph drawing checkers......Page 1174
Incremental graph drawing......Page 1175
Fixed parameter tractability......Page 1176
52.7 Sources and related material......Page 1177
References......Page 1178
53.1 Tensor product surfaces......Page 1183
Glossary......Page 1184
Parametric bezier and b-splines......Page 1185
Coons patches and gordon surfaces......Page 1186
Multisided patches......Page 1187
S-patches......Page 1188
Multivariate box splines and simplex splines......Page 1189
Main results......Page 1190
A-splines......Page 1191
Simplex- and box-based schemes......Page 1192
Main algorithms......Page 1194
Hierarchical splines......Page 1195
Differential equations and surface splines......Page 1196
References......Page 1198
Glossary......Page 3
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