Discrete and Computational Geometry: The Goodman-Pollack Festschrift

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
The Minimal Number of Triangles Needed to Span a Polygon Embedded in ℝ d ....Pages 509-526
Jacobi Decomposition and Eigenvalues of Symmetric Matrices....Pages 527-550
Discrete Geometry on Red and Blue Points in the Plane — A Survey —....Pages 551-570
Configurations with Rational Angles and Trigonometric Diophantine Equations....Pages 571-595
Reconstructing Sets From Interpoint Distances....Pages 597-631
Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio....Pages 633-650
Colorings and Homomorphisms of Minor Closed Classes....Pages 651-664
Conflict-free Colorings....Pages 665-671
New Complexity Bounds for Cylindrical Decompositions of Sub-Pfaffian Sets....Pages 673-694
Note on the Chromatic Number of the Space....Pages 695-698
Expansive Motions and the Polytope of Pointed Pseudo-Triangulations....Pages 699-736
Some Recent Quantitative and Algorithmic Results in Real Algebraic Geometry....Pages 737-749
A Discrete Isoperimetric Inequality and Its Application to Sphere Packings....Pages 751-765
On the Number of Maximal Regular Simplices Determined by n Points in Rd....Pages 767-787
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem....Pages 789-797
Quantizing Using Lattice Intersections....Pages 799-824
Note on a Generalization of Roth’s Theorem....Pages 825-827
Arrangements, Equivariant Maps and Partitions of Measures by k -Fans....Pages 829-848
Qualitative Infinite Version of Erdős’ Problem About Empty Polygons....Pages 849-853