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