Handbook of discrete and computational geometry

Cover......Page 1
Half Title......Page 2
Abstract......Page 3
Title......Page 8
Copyrights......Page 9
Table Of Contents......Page 10
Prefaces......Page 12
Contributors......Page 16
Part I. Combinatorial And Discrete Geometry......Page 24
Chapter 1. Finite Point Con Gurations (j. Pach)......Page 26
Chapter 2. Packing And Covering (g. Fejes T Oth)......Page 50
Chapter 3. Tilings (e. Harriss, D. Schattschneider, And M. Senechal)......Page 90
Chapter 4. Helly-type Theorems And Geometric Transversals (a. Holmsen And R. Wenger)......Page 114
Chapter 5. Pseudoline Arrangements (s. Felsner And J.e. Goodman)......Page 148
Chapter 6. Oriented Matroids (j. Richter-gebert And G.m. Ziegler)......Page 182
Chapter 7. Lattice Points And Lattice Polytopes (a. Barvinok)......Page 208
Chapter 8. Low-distortion Embeddings Of  Nite Metric Spaces  (p. Indyk, J. Matou Sek, And A. Sidiropoulos)......Page 234
Chapter 9. Geometry And Topology Of Polygonal Linkages (r. Connelly And E.d. Demaine)......Page 256
Chapter 10. Geometric Graph Theory (j. Pach)......Page 280
Chapter 11. Euclidean Ramsey Theory (r.l. Graham)......Page 304
Chapter 12. Discrete Aspects Of Stochastic Geometry (r. Schneider)......Page 322
Chapter 13. Geometric Discrepancy Theory And Uniform Distribution  (j.r. Alexander, J. Beck, And W.w.l. Chen)......Page 354
Chapter 14. Polyominoes (g. Barequet, S.w. Golomb, And D.a. Klarner)......Page 382
Part II. Polytopes And Polyhedra......Page 404
Chapter 15. Basic Properties Of Convex Polytopes  (m. Henk, J. Richter-gebert, And G.m. Ziegler)......Page 406
Chapter 16. Subdivisions And Triangulations Of Polytopes (c.w. Lee And F. Santos)......Page 438
Chapter 17. Face Numbers Of Polytopes And Complexes (l.j. Billera And A. Bj Orner)......Page 472
Chapter 18. Symmetry Of Polytopes And Polyhedra (e. Schulte)......Page 500
Chapter 19. Polytope Skeletons And Paths (g. Kalai)......Page 528
Chapter 20. Polyhedral Maps (u. Brehm And E. Schulte)......Page 556
Part III. Combinatorial And Computational Topology......Page 572
Chapter 21. Topological Methods In Discrete Geometry (r.t.  Zivaljevi C)......Page 574
Chapter 22. Random Simplicial Complexes (m. Kahle)......Page 604
Chapter 23. Computational Topology Of Graphs On Surfaces (e. Colin De Verdi Ere)......Page 628
Chapter 24. Persistent Homology (h. Edelsbrunner And D. Morozov)......Page 660
Chapter 25. High-dimensional Topological Data Analysis (f. Chazal)......Page 686
Part IV. Algorithms And Complexity Of  Fundamental Geometric Objects......Page 708
Chapter 26. Convex Hull Computations (r. Seidel)......Page 710
Chapter 27. Voronoi Diagrams And Delaunay Triangulations (s. Fortune)......Page 728
Chapter 28. Arrangements (d. Halperin And M. Sharir)......Page 746
Chapter 29. Triangulations And Mesh Generation (m. Bern, J. Shewchuk, And N. Amenta)......Page 786
Chapter 30. Polygons (j. O\'rourke, S. Suri, And C.d. T Oth)......Page 810
Chapter 31. Shortest Paths And Networks (j.s.b. Mitchell)......Page 834
Chapter 32. Proximity Algorithms (j.s.b. Mitchell And W. Mulzer)......Page 872
Chapter 33. Visibility (j. O\'rourke)......Page 898
Chapter 34. Geometric Reconstruction Problems (y. Disser And S.s. Skiena)......Page 920
Chapter 35. Curve And Surface Reconstruction (t.k. Dey)......Page 938
Chapter 36. Computational Convexity (p. Gritzmann And V. Klee)......Page 960
Chapter 37. Computational And Quantitative Real Algebraic Geometry  (s. Basu And B. Mishra)......Page 992
Part V. Geometric Data Structures And Searching......Page 1026
Chapter 38. Point Location (j. Snoeyink)......Page 1028
Chapter 39. Collision And Proximity Queries (y. Kim, M.c. Lin, And D. Manocha)......Page 1052
Chapter 40. Range Searching (p.k. Agarwal)......Page 1080
Chapter 41. Ray Shooting And Lines In Space (m. Pellegrini)......Page 1116
Chapter 42. Geometric Intersection (d.m. Mount)......Page 1136
Chapter 43. Nearest Neighbors In High-dimensional Spaces (a. Andoni And P. Indyk)......Page 1158
Part VI. Computational Techniques......Page 1180
Chapter 44. Randomizaton And Derandomization  (o. Cheong, K. Mulmuley, And E. Ramos)......Page 1182
Chapter 45. Robust Geometric Computation (v. Sharma And C.k. Yap)......Page 1212
Chapter 46. Parallel Algorithms In Geometry (m.t. Goodrich And N. Sitchinava)......Page 1248
Chapter 47. Epsilon-approximations And Epsilon-nets (n. Mustafa And K. Varadarajan)......Page 1264
Chapter 48. Coresets And Sketches (j. Phillips)......Page 1292
Part VII. Applications Of Discrete And Computational Geometry......Page 1312
Chapter 49. Linear Programming (m. Dyer, B. G Artner, N. Megiddo, And E. Welzl)......Page 1314
Chapter 50. Algorithmic Motion Planning (d. Halperin, O. Salzman, And M. Sharir)......Page 1334
Chapter 51. Robotics (d. Halperin, L.e. Kavraki, And K. Solovey)......Page 1366
Chapter 52. Computer Graphics (d. Dobkin And S. Teller)......Page 1400
Chapter 53 Modeling Motion (l.j. Guibas And M. Roeloffzen)......Page 1424
Chapter 54. Pattern Recognition (j. O\'rourke And G.t. Toussaint)......Page 1444
Chapter 55. Graph Drawing (e. Di Giacomo, G. Liotta, And R. Tamassia)......Page 1474
Chapter 56. Splines And Geometric Modeling (c.l. Bajaj)......Page 1502
Chapter 57. Solid Modeling (c.m. Hoffmann And V. Shapiro)......Page 1526
Chapter 58. Computation Of Robust Statistics: Depth, Median, And Related Measures  (p.j. Rousseeuw And M. Hubert)......Page 1564
Chapter 59. Geographic Information Systems (m. Van Kreveld)......Page 1578
Chapter 60. Geometric Applications Of The Grassmann-cayley Algebra (n.l. White)......Page 1604
Chapter 61. Rigidity And Scene Analysis (b. Schulze And W. Whiteley)......Page 1616
Chapter 62. Rigidity Of Symmetric Frameworks (b. Schulze And W. Whiteley)......Page 1656
Chapter 63. Global Rigidity (t. Jord An And W. Whiteley)......Page 1684
Chapter 64. Crystals, Periodic And Aperiodic (m. Senechal)......Page 1718
Chapter 65. Applications To Structural Molecular Biology (h. Edelsbrunner And P. Koehl)......Page 1732
Chapter 66. Geometry And Topology Of Genomic (a.j. Blumberg And R. Rabad An)......Page 1760
Part VIII. Geometric Software......Page 1800
Chapter 67. Software (m. Joswig And B. Lorenz)......Page 1802
Chapter 68. Two Computational Geometry Libraries: Leda And Cgal  (m. Hoffmann, L. Kettner, And S. N Aher)......Page 1822
Index Of Cited Authors......Page 1856
Index Of De Ned Terms......Page 1908