Discrete geometry

A collection of circles and the corresponding unit disk graph

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

Discrete geometry has large overlap with convex geometry and computational geometry, and is closely related to subjects such as finite geometry, combinatorial optimization, digital geometry, discrete differential geometry, geometric graph theory, toric geometry, and combinatorial topology.

History

Although polyhedra and tessellations have been studied for many years by people such as Kepler and Cauchy, modern discrete geometry has its origins in the late 19th century. Early topics studied were: the density of circle packings by Thue, projective configurations by Reye and Steinitz, the geometry of numbers by Minkowski, and map colourings by Tait, Heawood, and Hadwiger.

Topics in discrete geometry

• Polyhedra and polytopes
  • Polyhedral combinatorics
  • Lattice polytopes
  • Ehrhart polynomials
  • Pick's theorem
  • Hirsch conjecture

• Packings, coverings and tilings
  • Circle packings
  • Sphere packings
  • Kepler conjecture
  • Quasicrystals
  • Aperiodic tilings
  • Periodic Graphs (Geometry)

• Structural rigidity and flexibility
  • Cauchy's theorem
  • Flexible polyhedra

• Incidence structures
  • Configurations
  • Line arrangements
  • Hyperplane arrangements
  • Buildings

• Oriented matroids

• Geometric graph theory
  • Graph drawing
  • Polyhedral graphs
  • Voronoi diagrams and Delaunay triangulations

• Simplicial complexes

• Topological combinatorics
  • Sperner's lemma
  • Regular maps

• Lattices and discrete groups
  • Reflection groups
  • Triangle groups
• Digital geometry
• Discrete differential geometry

• Geometric set partitioning and transversals

See also

• Discrete and Computational Geometry
• Discrete mathematics
• Paul Erdős

References

• Bezdek, András, (2003). Discrete geometry: in honor of W. Kuperberg's 60th birthday. New York, N.Y: Marcel Dekker. ISBN 0-8247-0968-3. 
• Bezdek, Károly (2010). Classical Topics in Discrete Geometry. New York, N.Y: Springer. ISBN 978-1-4419-0599-4. 
• Bezdek, Károly (2013). Lectures on Sphere Arrangements - the Discrete Geometric Side. New York, N.Y: Springer. ISBN 978-1-4614-8117-1. 
• Bezdek, Károly; Deza, Antoine; Ye, Yinyu (2013). Discrete Geometry and Optimization. New York, N.Y: Springer. ISBN 978-3-319-00200-2. 
• Brass, Peter; Moser, William; Pach, János (2005). Research problems in discrete geometry. Berlin: Springer. ISBN 0-387-23815-8. 
• Pach, János; Agarwal, Pankaj K. (1995). Combinatorial geometry. New York: Wiley-Interscience. ISBN 0-471-58890-3. 
• Goodman, Jacob E. and O'Rourke, Joseph (2004). Handbook of Discrete and Computational Geometry, Second Edition. Boca Raton: Chapman & Hall/CRC. ISBN 1-58488-301-4. 
• Gruber, Peter M. (2007). Convex and Discrete Geometry. Berlin: Springer. ISBN 3-540-71132-5. 
• Matoušek, Jiří (2002). Lectures on discrete geometry. Berlin: Springer. ISBN 0-387-95374-4. 
• Vladimir Boltyanski, Horst Martini, Petru S. Soltan, (1997). Excursions into Combinatorial Geometry. Springer. ISBN 3-540-61341-2.