Research Problems in Discrete Geometry

Preface......Page 5
Preface to an Earlier Version of RPDG......Page 7
Contents......Page 10
0. Defintions and Notations......Page 14
1.1 Basic Questions and Defnitions......Page 18
1.2 The Least Economical Convex Sets for Packing......Page 23
1.3 The Least Economical Convex Sets for Covering......Page 28
1.4 How Economical Are the Lattice Arrangements?......Page 32
1.5 Packing with Semidisks, and the Role of Symmetry......Page 36
1.6 Packing Equal Circles into Squares, Circles, Spheres......Page 41
1.7 Packing Equal Circles or Squares in a Strip......Page 57
1.8 The Densest Packing of Spheres......Page 61
1.9 The Densest Packings of Specifc Convex Bodies......Page 69
1.10 Linking Packing and Covering Densities......Page 74
1.11 Sausage Problems and Catastrophes......Page 80
2.1 Decomposition of Multiple Packings and Coverings......Page 88
2.2 Solid and Saturated Packings and Reduced Coverings......Page 94
2.3 Stable Packings and Coverings......Page 101
2.4 Kissing and Neighborly Convex Bodies......Page 106
2.5 Thin Packings with Many Neighbors......Page 119
2.6 Permeability and Blocking Light Rays......Page 128
3.1 Potato Bag Problems......Page 134
3.2 Covering a Convex Body with Its Homothetic Copies......Page 144
3.3 Levi-Hadwiger Covering Problem and Illumination......Page 149
3.4 Covering a Ball by Slabs......Page 156
3.5 Point Trapping and Impassable Lattice Arrangements......Page 162
4.1 Tiling the Plane with Congruent Regions......Page 174
4.2 Aperiodic Tilings and Tilings with Fivefold Symmetry......Page 183
4.3 Tiling Space with Polytopes......Page 189
5.1 The Maximum Number of Unit Distances in the Plane......Page 196
5.2 The Number of Equal Distances in Other Spaces......Page 204
5.3 The Minimum Number of Distinct Distances in the Plane......Page 213
5.4 The Number of Distinct Distances in Other Spaces......Page 222
5.5 Repeated Distances in Point Sets in General Position......Page 227
5.6 Repeated Distances in Point Sets in Convex Position......Page 230
5.7 Frequent Small Distances and Touching Pairs......Page 235
5.8 Frequent Large Distances......Page 243
5.9 Chromatic Number of Unit-Distance Graphs......Page 247
5.10 Further Problems on Repeated Distances......Page 258
5.11 Integral or Rational Distances......Page 261
6.1 Repeated Simplices and Other Patterns......Page 272
6.2 Repeated Directions, Angles, Areas......Page 283
6.3 Euclidean Ramsey Problems......Page 293
7.1 The Maximum Number of Incidences......Page 302
7.2 Sylvester–Gallai-Type Problems......Page 315
7.3 Line Arrangements Spanned by a Point Set......Page 324
8.1 Structure of the Space of Order Types......Page 338
8.2 Convex Polygons and the Erd os–Szekeres Problem......Page 342
8.3 Halving Lines and Related Problems......Page 358
8.4 Extremal Number of Special Subconfgurations......Page 367
8.5 Other Problems on Points in General Position......Page 377
9.1 Graph Drawings......Page 386
9.2 Drawing Planar Graphs......Page 388
9.3 The Crossing Number......Page 396
9.4 Other Crossing Numbers......Page 402
9.5 From Thrackles to Forbidden Geometric Subgraphs......Page 409
9.6 Further Tur´an-Type Problems......Page 414
9.7 Ramsey-Type Problems......Page 421
9.8 Geometric Hypergraphs......Page 427
10.1 Packing Lattice Points in Subspaces......Page 430
10.2 Covering Lattice Points by Subspaces......Page 435
10.3 Sets of Lattice Points Avoiding Other Regularities......Page 438
10.4 Visibility Problems for Lattice Points......Page 443
11.1 Isoperimetric Inequalities for Polygons and Polytopes......Page 448
11.2 Heilbronn-Type Problems......Page 456
11.3 Circumscribed and Inscribed Convex Sets......Page 464
11.4 Universal Covers......Page 470
11.5 Approximation Problems......Page 479
Author Index......Page 486
Subject Index......Page 504