Discrete geometry
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 a 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.
Contents
 1 History

2 Topics in discrete geometry
 2.1 Polyhedra and polytopes
 2.2 Packings, coverings and tilings
 2.3 Structural rigidity and flexibility
 2.4 Incidence structures
 2.5 Oriented matroids
 2.6 Geometric graph theory
 2.7 Simplicial complexes
 2.8 Topological combinatorics
 2.9 Lattices and discrete groups
 2.10 Digital geometry
 2.11 Discrete differential geometry
 3 See also
 4 Notes
 5 References
 6 External links
History
Although polyhedra and tessellations had 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.
László Fejes Tóth, H.S.M. Coxeter and Paul Erdős, laid the foundations of discrete geometry. ^{[1]}^{[2]}^{[3]}
Topics in discrete geometry
Polyhedra and polytopes
A polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions (such as a 4polytope in four dimensions). Some theories further generalize the idea to include such objects as unbounded polytopes (apeirotopes and tessellations), and abstract polytopes.
The following are some of the aspects of polytopes studied in discrete geometry:
Packings, coverings and tilings
Packings, coverings, and tilings are all ways of arranging uniform objects (typically circles, spheres, or tiles) in a regular way on a surface or manifold.
A sphere packing is an arrangement of nonoverlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually threedimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, ndimensional Euclidean space (where the problem becomes circle packing in two dimensions, or hypersphere packing in higher dimensions) or to nonEuclidean spaces such as hyperbolic space.
A tessellation of a flat surface is the tiling of a plane using one or more geometric shapes, called tiles, with no overlaps and no gaps. In mathematics, tessellations can be generalized to higher dimensions.
Specific topics in this area include:
 Circle packings
 Sphere packings
 Kepler conjecture
 Quasicrystals
 Aperiodic tilings
 Periodic graph
 Finite subdivision rules
Structural rigidity and flexibility
Structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.
Topics in this area include:
Incidence structures
Incidence structures generalize planes (such as affine, projective, and Möbius planes) as can be seen from their axiomatic definitions. Incidence structures also generalize the higherdimensional analogs and the finite structures are sometimes called finite geometries.
Formally, an incidence structure is a triple
where P is a set of "points", L is a set of "lines" and is the incidence relation. The elements of are called flags. If
we say that point p "lies on" line .
Topics in this area include:
Oriented matroids
An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of arrangements of vectors in a vector space over an ordered field (particularly for partially ordered vector spaces).^{[4]} In comparison, an ordinary (i.e., nonoriented) matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered.^{[5]}^{[6]}
Geometric graph theory
A geometric graph is a graph in which the vertices or edges are associated with geometric objects. Examples include Euclidean graphs, the 1skeleton of a polyhedron or polytope, intersection graphs, and visibility graphs.
Topics in this area include:
Simplicial complexes
A simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their ndimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set appearing in modern simplicial homotopy theory. The purely combinatorial counterpart to a simplicial complex is an abstract simplicial complex.
Topological combinatorics
The discipline of combinatorial topology used combinatorial concepts in topology and in the early 20th century this turned into the field of algebraic topology.
In 1978 the situation was reversed – methods from algebraic topology were used to solve a problem in combinatorics – when László Lovász proved the Kneser conjecture, thus beginning the new study of topological combinatorics. Lovász's proof used the BorsukUlam theorem and this theorem retains a prominent role in this new field. This theorem has many equivalent versions and analogs and has been used in the study of fair division problems.
Topics in this area include:
Lattices and discrete groups
A discrete group is a group G equipped with the discrete topology. With this topology, G becomes a topological group. A discrete subgroup of a topological group G is a subgroup H whose relative topology is the discrete one. For example, the integers, Z, form a discrete subgroup of the reals, R (with the standard metric topology), but the rational numbers, Q, do not.
A lattice in a locally compact topological group is a discrete subgroup with the property that the quotient space has finite invariant measure. In the special case of subgroups of R^{n}, this amounts to the usual geometric notion of a lattice, and both the algebraic structure of lattices and the geometry of the totality of all lattices are relatively well understood. Deep results of Borel, HarishChandra, Mostow, Tamagawa, M. S. Raghunathan, Margulis, Zimmer obtained from the 1950s through the 1970s provided examples and generalized much of the theory to the setting of nilpotent Lie groups and semisimple algebraic groups over a local field. In the 1990s, Bass and Lubotzky initiated the study of tree lattices, which remains an active research area.
Topics in this area include:
Digital geometry
Digital geometry deals with discrete sets (usually discrete point sets) considered to be digitized models or images of objects of the 2D or 3D Euclidean space.
Simply put, digitizing is replacing an object by a discrete set of its points. The images we see on the TV screen, the raster display of a computer, or in newspapers are in fact digital images.
Its main application areas are computer graphics and image analysis. ^{[7]}
Discrete differential geometry
Discrete differential geometry is the study of discrete counterparts of notions in differential geometry. Instead of smooth curves and surfaces, there are polygons, meshes, and simplicial complexes. It is used in the study of computer graphics and topological combinatorics.
Topics in this area include:
 Discrete Laplace operator
 Discrete exterior calculus
 Discrete Morse theory
 Topological combinatorics
 Spectral shape analysis
 Abstract differential geometry
 Analysis on fractals
See also
Notes
 ^ Pach, János; et al. (2008), Intuitive Geometry, in Memoriam László Fejes Tóth, Alfréd Rényi Institute of Mathematics
 ^ Katona, G. O. H. (2005), "Laszlo Fejes Toth – Obituary", Studia Scientiarum Mathematicarum Hungarica, 42 (2): 113
 ^ Bárány, Imre (2010), "Discrete and convex geometry", in Horváth, János, A Panorama of Hungarian Mathematics in the Twentieth Century, I, New York: Springer, pp. 431–441, ISBN 9783540307211
 ^ Rockafellar 1969. Björner et alia, Chapters 13. Bokowski, Chapter 1. Ziegler, Chapter 7.
 ^ Björner et alia, Chapters 13. Bokowski, Chapters 14.
 ^ Because matroids and oriented matroids are abstractions of other mathematical abstractions, nearly all the relevant books are written for mathematical scientists rather than for the general public. For learning about oriented matroids, a good preparation is to study the textbook on linear optimization by Nering and Tucker, which is infused with orientedmatroid ideas, and then to proceed to Ziegler's lectures on polytopes.
 ^ See Li Chen, Digital and discrete geometry: Theory and Algorithms, Springer, 2014.
References
 Bezdek, András, (2003). Discrete geometry: in honor of W. Kuperberg's 60th birthday. New York, N.Y: Marcel Dekker. ISBN 0824709683.
 Bezdek, Károly (2010). Classical Topics in Discrete Geometry. New York, N.Y: Springer. ISBN 9781441905994.
 Bezdek, Károly (2013). Lectures on Sphere Arrangements  the Discrete Geometric Side. New York, N.Y: Springer. ISBN 9781461481171.
 Bezdek, Károly; Deza, Antoine; Ye, Yinyu (2013). Discrete Geometry and Optimization. New York, N.Y: Springer. ISBN 9783319002002.
 Brass, Peter; Moser, William; Pach, János (2005). Research problems in discrete geometry. Berlin: Springer. ISBN 0387238158.
 Pach, János; Agarwal, Pankaj K. (1995). Combinatorial geometry. New York: WileyInterscience. ISBN 0471588903.
 Goodman, Jacob E. and O'Rourke, Joseph (2004). Handbook of Discrete and Computational Geometry, Second Edition. Boca Raton: Chapman & Hall/CRC. ISBN 1584883014.
 Gruber, Peter M. (2007). Convex and Discrete Geometry. Berlin: Springer. ISBN 3540711325.
 Matoušek, Jiří (2002). Lectures on discrete geometry. Berlin: Springer. ISBN 0387953744.
 Vladimir Boltyanski, Horst Martini, Petru S. Soltan, (1997). Excursions into Combinatorial Geometry. Springer. ISBN 3540613412.