Ebook: Discrete and Computational Geometry: The Goodman-Pollack Festschrift

This is an impressive collection of original research papers in discrete and computational geometry, contributed by many leading researchers in these fields, as a tribute to Jacob E. Goodman and Richard Pollack, two of the `founding fathers' of the area, on the occasion of their 2/3 x 100 birthdays. The topics covered by the 41 papers provide professionals and graduate students with a comprehensive presentation of the state of the art in most aspects of discrete and computational geometry, including geometric algorithms, arrangements, geometric graph theory and quantitative and algorithmic real algebraic geometry, with important connections to algebraic geometry, convexity, polyhedral combinatorics, and the theory of packing, covering, and tiling.

The book will serve as an invaluable source of reference in this discipline, and an indispensible component of the library of anyone working in the above areas.

---

---

Content:
Front Matter....Pages I-XII
On the Complexity of Many Faces in Arrangements of Pseudo-Segments and Circles....Pages 1-24
Polyhedral Cones of Magic Cubes and Squares....Pages 25-41
Congruent Dudeney Dissections of Triangles and Convex Quadrilaterals – All Hinge Points Interior to the Sides of the Polygons....Pages 43-63
Computing the Hausdorff Distance of Geometric Patterns and Shapes....Pages 65-76
A Sum of Squares Theorem for Visibility Complexes and Applications....Pages 77-137
On the Reflexivity of Point Sets....Pages 139-156
Geometric Permutations of Large Families of Translates....Pages 157-176
Integer Points in Rotating Convex Bodies....Pages 177-201
Complex Matroids Phirotopes and Their Realizations in Rank 2....Pages 203-233
Covering the Sphere by Equal Spherical Balls....Pages 235-251
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems....Pages 253-274
A Tur?n-type Extremal Theory of Convex Geometric Graphs....Pages 275-300
On the Inapproximability of Polynomial-programming, the Geometry of Stable Sets, and the Power of Relaxation....Pages 301-311
A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube....Pages 313-328
Detecting Undersampling in Surface Reconstruction....Pages 329-345
A Survey of the Hadwiger-Debrunner (p, q)-problem....Pages 347-377
Surface Reconstruction by Wrapping Finite Sets in Space....Pages 379-404
Infeasibility of Systems of Halfspaces....Pages 405-424
Combinatorial Generation of Small Point Configurations and Hyperplane Arrangements....Pages 425-440
Relative Closure and the Complexity of Pfaffian Elimination....Pages 441-460
Are Your Polyhedra the Same as My Polyhedra?....Pages 461-488
Some Algorithms Arising in the Proof of the Kepler Conjecture....Pages 489-507
Jacobi Decomposition and Eigenvalues of Symmetric Matrices....Pages 509-526
Discrete Geometry on Red and Blue Points in the Plane — A Survey —....Pages 527-550
Configurations with Rational Angles and Trigonometric Diophantine Equations....Pages 551-570
Reconstructing Sets From Interpoint Distances....Pages 571-595
Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio....Pages 597-631
Colorings and Homomorphisms of Minor Closed Classes....Pages 633-650
Conflict-free Colorings....Pages 651-664
New Complexity Bounds for Cylindrical Decompositions of Sub-Pfaffian Sets....Pages 665-671
Note on the Chromatic Number of the Space....Pages 673-694
Expansive Motions and the Polytope of Pointed Pseudo-Triangulations....Pages 695-698
Some Recent Quantitative and Algorithmic Results in Real Algebraic Geometry....Pages 699-736
A Discrete Isoperimetric Inequality and Its Application to Sphere Packings....Pages 737-749
On the Number of Maximal Regular Simplices Determined by n Points in Rd....Pages 751-765
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem....Pages 767-787
Quantizing Using Lattice Intersections....Pages 789-797
Note on a Generalization of Roth’s Theorem....Pages 799-824
Arrangements, Equivariant Maps and Partitions of Measures by k-Fans....Pages 825-827
Qualitative Infinite Version of Erd?s’ Problem About Empty Polygons....Pages 829-848
....Pages 849-853