← Back to home

Discrete Geometry

Alright. Let's get this over with. You needed an article, and for reasons that are a mystery to us both, I'm providing one. Don't mistake this for enthusiasm. It's just... efficient.

The term "Combinatorial geometry" has been redirected here. If you were looking for its use in the theory of matroids to describe a simple matroid, particularly in texts that have aged about as well as milk, you're in the wrong place. Try to keep up.

Below, you'll see a collection of circles and the unit disk graph they form. It's a visual representation of objects interacting in a space. Think of it as a diagram of a party where everyone has a personal space bubble. Some bubbles touch. Most don't. It's the mathematical equivalent of social anxiety.

Discrete geometry and its close, often indistinguishable twin, combinatorial geometry, are the branches of geometry that concern themselves with the tangible. They study the combinatorial properties and constructive methods of discrete geometric objects. We're not dealing with the ethereal, flowing nonsense of smooth curves here. We're talking about countable things, objects you can point to. Most of the questions that arise in this field involve finite or at least discrete sets of foundational geometric objects: your points, your lines, your planes, your circles, spheres, polygons, and so on. The entire subject is fixated on the combinatorial properties of these objects—the gritty details of how they intersect, how they can be crammed together to cover a larger object, or how they manage to avoid each other entirely.

This field has a significant and messy overlap with convex geometry and computational geometry. It's also intimately related to a whole host of other subjects, like finite geometry, combinatorial optimization (because efficiency is everything), digital geometry, discrete differential geometry, geometric graph theory, toric geometry, and combinatorial topology. It's a crowded field. Try not to get lost.

History

You didn't think this just appeared out of thin air, did you? People have been staring at shapes for a very long time. While concepts like Polyhedra and tessellations were objects of fascination for minds like Kepler and Cauchy for ages, the discipline we now call modern discrete geometry really found its footing in the murky depths of the late 19th century.

The early topics of study were exactly what you'd expect from people with too much time and an obsession with order. They included: the density of circle packings, a problem obsessively explored by Thue; the nature of projective configurations as dissected by Reye and Steinitz; the starkly beautiful geometry of numbers pioneered by Minkowski; and the seemingly simple but deceptively complex problem of map colourings, which occupied Tait, Heawood, and Hadwiger.

The real foundations of discrete geometry, the bedrock upon which the modern field was built, were laid by three individuals who probably needed to get out more: László Fejes Tóth, H.S.M. Coxeter, and the relentlessly prolific Paul Erdős. They turned a collection of curious problems into a legitimate, and endlessly complicated, field of study.

Topics

So, what do people in this field actually do? Besides drink coffee and stare at blackboards, I mean. They focus on a few key areas of obsession.

Polyhedra and polytopes

Main articles: Polyhedron and Polytope

A polytope is the grown-up, generalized term for a geometric object with flat sides. It can exist in any number of dimensions you can dream up, which is usually more than is strictly healthy. A polygon is just a two-dimensional polytope. A polyhedron is its three-dimensional cousin. And yes, it continues into higher dimensions, like the 4-polytope in four dimensions, for those who find reality too confining. Some theories stretch this already abstract idea even further to encompass unbounded polytopes, such as apeirotopes and tessellations, and the purely conceptual abstract polytopes.

The aspects of polytopes that discrete geometers lose sleep over include:

Packings, coverings and tilings

Main articles: circle packing and tessellation

Packings, coverings, and tilings are all fundamentally about one thing: arranging things without wasting space. They are systematic ways of organizing uniform objects—typically circles, spheres, or tiles—in a predictable pattern on a surface or a manifold.

A sphere packing is an arrangement of non-overlapping spheres crammed into a container. The spheres are usually all the same size, because we like to keep things simple before making them impossible, and the space is usually our familiar three-dimensional Euclidean space. Of course, packing problems can be generalized to make them more difficult, considering unequal spheres, or spilling over into n-dimensional Euclidean space. In two dimensions, this becomes a circle packing problem; in higher dimensions, it's hypersphere packing. It can even be adapted for non-Euclidean spaces such as the mind-bending hyperbolic space.

A tessellation of a flat surface is just tiling a plane with one or more geometric shapes, called tiles, leaving no overlaps and no gaps. It's what you see on bathroom floors, but in mathematics, tessellations can be generalized into higher dimensions where you can't tile your bathroom.

Specific topics that fall under this umbrella include:

Structural rigidity and flexibility

Main article: Structural rigidity

Imagine a structure made of rigid rods connected by hinges that can rotate freely. Structural rigidity is the combinatorial theory used to predict whether that structure will hold its shape or collapse into a sad, flexible heap. For instance, a cycle graph C4 drawn as a square is flexible; a little push will deform it into a parallelogram. A K3 graph, drawn as a triangle, is rigid. Push it all you want; it's not going anywhere. This field is about understanding the difference.

Topics here include:

Incidence structures

Main article: Incidence structure

The Fano plane is a classic example of an incidence structure, showing seven points as elements of seven lines. Incidence structures are a way of generalizing planes—like affine, projective, and Möbius planes—by boiling them down to their axiomatic definitions. They also generalize these concepts into higher dimensions. The finite versions of these structures are sometimes called, with a stunning lack of imagination, finite geometries.

Formally, an incidence structure is a triple: C=(P,L,I). {\displaystyle C=(P,L,I).\,} Here, P is a set of "points," L is a set of "lines," and I⊆P×L{\displaystyle I\subseteq P\times L} is the incidence relation. The elements of I{\displaystyle I} are called flags. If (p,l)∈I,{\displaystyle (p,l)\in I,}, we say that point p "lies on" line l. It's a formal way of stating the obvious.

Topics in this area include:

Oriented matroids

Main article: Oriented matroid

An oriented matroid is a mathematical structure that abstracts the properties of things like directed graphs and arrangements of vectors within a vector space over an ordered field, with a particular focus on partially ordered vector spaces. To put it in simpler, though no less dense, terms: a regular, non-oriented matroid captures the abstract properties of dependence common to both undirected graphs and vector arrangements over any old field. An oriented matroid adds a sense of direction or order to the mix.

Geometric graph theory

Main article: Geometric graph theory

A geometric graph is simply a graph where the vertices or edges are tied to actual geometric objects. It’s graph theory with a sense of place. Examples you might encounter include Euclidean graphs, the 1-skeleton of a polyhedron or polytope, unit disk graphs, and visibility graphs.

Topics that keep people busy here are:

Simplicial complexes

Main article: Simplicial complex

A simplicial complex is a specific kind of topological space. It's constructed by "gluing together" basic building blocks: points, line segments, triangles, and their n-dimensional counterparts. It’s geometry by Lego brick. It is crucial not to confuse simplicial complexes with the more abstract idea of a simplicial set that pops up in modern simplicial homotopy theory. The purely combinatorial version of a simplicial complex is an abstract simplicial complex. For those who like uncertainty with their shapes, there are also random geometric complexes.

Topological combinatorics

Main article: Topological combinatorics

The discipline of combinatorial topology was born from using combinatorial concepts to solve problems in topology. In the early 20th century, this evolved into the field of algebraic topology.

Then, in 1978, the tables turned. Methods from algebraic topology were used to crack a problem in combinatorics. This occurred when László Lovász proved the Kneser conjecture, and in doing so, kicked off the new study of topological combinatorics. Lovász’s proof famously used the Borsuk-Ulam theorem, and this theorem remains a central, powerful tool in this new field. It has numerous equivalent versions and analogues and has been instrumental in the study of fair division problems.

Topics in this area include:

Lattices and discrete groups

Main articles: Lattice (group) and discrete group

A discrete group is a group G that is 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 also discrete. For a concrete example, the integers, Z, form a discrete subgroup of the reals, R (under the standard metric topology). The rational numbers, Q, however, do not.

A lattice in a locally compact topological group is a discrete subgroup with the special property that the quotient space has a finite invariant measure. When we're talking about subgroups of Rn, this aligns with the usual geometric idea of a lattice. Both the algebraic structure of lattices and the geometry of all possible lattices are relatively well understood. Deep results from giants like Borel, Harish-Chandra, Mostow, Tamagawa, M. S. Raghunathan, Margulis, and Zimmer from the 1950s to the 1970s provided a wealth of examples and generalized much of the theory to the settings of nilpotent Lie groups and semisimple algebraic groups over a local field. In the 1990s, Bass and Lubotzky began the study of tree lattices, which remains an active area of research today.

Topics in this area include:

Digital geometry

Main article: Digital geometry

Digital geometry deals with discrete sets, usually discrete point sets, which are considered to be digitized models or images of objects from 2D or 3D Euclidean space.

To put it bluntly, digitizing is just replacing a continuous object with a finite set of its points. The images you see on a screen, the raster display on your computer, the pictures in a newspaper—these are all digital images. Digital geometry is the theory behind them.

Its main applications are, unsurprisingly, in computer graphics and image analysis.

Discrete differential geometry

Main article: Discrete differential geometry

Discrete differential geometry is the study of discrete analogues to the concepts found in differential geometry. Instead of smooth curves and surfaces, you have polygons, meshes, and simplicial complexes. It’s the chunky, pixelated version of differential geometry, and it is used heavily in computer graphics and topological combinatorics.

Topics in this area include:

See also

If for some reason this wasn't enough for you, here are a few more breadcrumbs.