Discrete geometry

Last updated
A collection of circles and the corresponding unit disk graph Unit disk graph.svg
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 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.


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]


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 4-polytope 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 non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, n-dimensional Euclidean space (where the problem becomes circle packing in two dimensions, or hypersphere packing in higher dimensions) or to non-Euclidean 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:

Structural rigidity and flexibility

Graphs are drawn as rods connected by rotating hinges. The cycle graph C4 drawn as a square can be tilted over by the blue force into a parallelogram, so it is a flexible graph. K3, drawn as a triangle, cannot be altered by any force that is applied to it, so it is a rigid graph. Structural rigidity basic examples.svg
Graphs are drawn as rods connected by rotating hinges. The cycle graph C4 drawn as a square can be tilted over by the blue force into a parallelogram, so it is a flexible graph. K3, drawn as a triangle, cannot be altered by any force that is applied to it, so it is a rigid graph.

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

Seven points are elements of seven lines in the Fano plane, an example of an incidence structure. Fano plane with nimber labels.svg
Seven points are elements of seven lines in the Fano plane, an example of an incidence structure.

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 higher-dimensional 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., non-oriented) 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 1-skeleton of a polyhedron or polytope, unit disk 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 n-dimensional 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. See also random geometric complexes.

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 Borsuk-Ulam 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 Rn, 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, Harish-Chandra, 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:

See also


  1. Pach, János; et al. (2008), Intuitive Geometry, in Memoriam László Fejes Tóth, Alfréd Rényi Institute of Mathematics
  2. Katona, G. O. H. (2005), "Laszlo Fejes Toth – Obituary", Studia Scientiarum Mathematicarum Hungarica, 42 (2): 113
  3. Bárány, Imre (2010), "Discrete and convex geometry", in Horváth, János (ed.), A Panorama of Hungarian Mathematics in the Twentieth Century, I, New York: Springer, pp. 431–441, ISBN   9783540307211
  4. Rockafellar 1969. Björner et alia, Chapters 1-3. Bokowski, Chapter 1. Ziegler, Chapter 7.
  5. Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.
  6. 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 oriented-matroid ideas, and then to proceed to Ziegler's lectures on polytopes.
  7. See Li Chen, Digital and discrete geometry: Theory and Algorithms, Springer, 2014.

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.

Discrete mathematics Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.

Polyhedron Three-dimensional shape with flat polygonal faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- + -hedron.

In elementary geometry, a polytope is a geometric object with "flat" sides. It is a generalization in any number of dimensions of the three-dimensional polyhedron. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. Flat sides mean that the sides of a (k+1)-polytope consist of k-polytopes that may have (k−1)-polytopes in common. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope.

Algebraic topology Branch of mathematics

Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify up to homotopy equivalence.

Simplicial complex

In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their n-dimensional counterparts. 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.

Geometric group theory

Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act.

Mathematics encompasses a growing variety and depth of subjects over history, and comprehension requires a system to categorize and organize the many subjects into more general areas of mathematics. A number of different classification schemes have arisen, and though they share some similarities, there are differences due in part to the different purposes they serve. In addition, as mathematics difficult by some subjects, often the most active, which straddle the boundary between different areas.

Triangulation (topology)

In mathematics, topology generalizes the notion of triangulation in a natural way as follows:

Convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

László Fejes Tóth was a Hungarian mathematician who specialized in geometry. He proved that a lattice pattern is the most efficient way to pack centrally symmetric convex sets on the Euclidean plane. He also investigated the sphere packing problem. He was the first to show, in 1953, that proof of the Kepler conjecture can be reduced to a finite case analysis and, later, that the problem might be solved using a computer.

Digital topology deals with properties and features of two-dimensional (2D) or three-dimensional (3D) digital images that correspond to topological properties or topological features of objects.

Algebraic combinatorics

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.


Polymake is software for the algorithmic treatment of convex polyhedra.

A Euclidean graph is periodic if there exists a basis of that Euclidean space whose corresponding translations induce symmetries of that graph. Equivalently, a periodic Euclidean graph is a periodic realization of an abelian covering graph over a finite graph. A Euclidean graph is uniformly discrete if there is a minimal distance between any two vertices. Periodic graphs are closely related to tessellations of space and the geometry of their symmetry groups, hence to geometric group theory, as well as to discrete geometry and the theory of polytopes, and similar areas.

Károly Bezdek Hungarian-Canadian mathematician

Károly Bezdek is a Hungarian-Canadian mathematician. He is a professor as well as a Canada Research Chair of mathematics and the director of the Centre for Computational and Discrete Geometry at the University of Calgary in Calgary, Alberta, Canada. Also he is a professor of mathematics at the University of Pannonia in Veszprém, Hungary. His main research interests are in geometry in particular, in combinatorial, computational, convex, and discrete geometry. He has authored 3 books and more than 130 research papers. He is a founding Editor-in-Chief of the e-journal Contributions to Discrete Mathematics (CDM).

In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

Flip graph

A flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.