Hubbry Logo
Discrete geometryDiscrete geometryMain
Open search
Discrete geometry
Community hub
Discrete geometry
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Discrete geometry
Discrete geometry
Discrete geometry
View on Wikipedia
from Wikipedia
Geometry
Stereographic projection from the top of a sphere onto a plane beneath it
Projecting a sphere to a plane
Branches
  • Concepts
  • Features
Dimension
Zero-dimensional
One-dimensional
Two-dimensional
Triangle
Quadrilateral
Circle
Three-dimensional
Polyhedron
Solid of revolution
Four-/other-dimensional
Geometers
by name
by period
BCE
1–1400s
1400s–1700s
1700s–1900s
Present day
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.

History

[edit]

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

[edit]

Polyhedra and polytopes

[edit]
Main articles: Polyhedron and Polytope

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

[edit]
Main articles: circle packing and tessellation

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

[edit]
Main article: Structural rigidity
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

[edit]
Main article: Incidence structure
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

[edit]
Main article: Oriented matroid

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

[edit]
Main article: 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

[edit]
Main article: Simplicial complex

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

[edit]
Main article: 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

[edit]
Main articles: Lattice (group) and discrete group

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

[edit]
Main article: 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

[edit]
Main article: 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

[edit]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Discrete geometry

View on Grokipedia
from Grokipedia
Discrete geometry is a branch of geometry that studies the combinatorial properties and constructive methods of discrete geometric objects, such as finite arrangements of points, lines, planes, polyhedra, and lattices in . It focuses on the arrangements and interactions of these discrete sets, often emphasizing convexity, packing, , and problems rather than continuous manifolds or curves. Unlike classical geometry, which deals with smooth and infinite structures, discrete geometry addresses finite or countable configurations, bridging and geometry through tools like convex hulls and separation theorems. The field has roots in classical problems dating back to the 17th century, such as Johannes Kepler's 1611 conjecture on the densest packing of spheres, which was rigorously proved by Thomas Hales in 1998 and published in 2005. Key foundational results include , which states that for a family of convex sets in Rd\mathbb{R}^d, if every d+1d+1 sets have nonempty intersection, then the entire family intersects, providing essential tools for intersection and covering problems. Other central concepts encompass lattice theory, where integer points in convex bodies are analyzed via theorems like those of Blichfeldt and Minkowski on successive minima and inhomogeneous minima; sphere packings and coverings; and Ehrhart polynomials, which count lattice points in dilates of polytopes. These elements often intersect with , as seen in Carathéodory's theorem, which asserts that any point in the of a set in Rd\mathbb{R}^d can be expressed as a convex combination of at most d+1d+1 points from the set. Discrete geometry's scope extends to polyhedral and surface structures, including rigidity theory—such as Cauchy's theorem on the congruence of convex polytopes with isometric faces—and topological methods for problems like the four-vertex theorem for curves. It also incorporates computational aspects, like the shortest vector problem in lattices, which is NP-hard and underlies algorithms such as the LLL reduction used in . Applications span diverse fields: in and for optimal sphere packings; in and modeling for surface parameterizations and triangulations; in brain imaging for geometric analysis of discrete data; and in for problems like Siegel's lemma in . Recent developments continue to explore connections to , Ricci flows on discrete surfaces, and statistical methods for ranking via combinatorial .

Introduction and Foundations

Definition and Scope

Discrete geometry is a branch of that investigates geometric objects and configurations through the lens of , prioritizing combinatorial, topological, and algebraic techniques rather than continuous analytic methods. It examines finite or countable structures embedded in Euclidean or other spaces, focusing on their qualitative properties and relationships. This approach contrasts with classical geometry by avoiding infinitesimal considerations, instead leveraging tools like and enumeration to uncover patterns and invariants. Central to discrete geometry are characteristics such as finite point sets in the plane or higher dimensions, configurations with integer coordinates like , and arrangements that may dispense with metric assumptions to emphasize combinatorial types. The field stresses problems of , , and , often asking how many such objects satisfy certain conditions or what their extremal properties are. Representative examples include finite sets of points in in the plane, where no three are collinear, and points within convex regions. Polyhedral arrangements, such as those formed by hyperplanes, illustrate how discrete structures partition into cells with countable . Discrete geometry overlaps considerably with and geometric combinatorics. The scope of discrete geometry excludes purely continuous phenomena, such as smooth curves without , but incorporates approximations or finite samplings of continuous objects, like lattice points approximating a circle. This includes the , pioneered by , which applies discrete methods to number-theoretic problems involving lattice points in convex bodies.

Relation to Continuous Geometry

Discrete geometry fundamentally differs from classical continuous geometry in its foundational assumptions and analytical tools. While continuous geometry operates on smooth manifolds using limits, derivatives, and measure theory to describe properties like and , discrete geometry focuses on finite or countable sets of points, lines, and polygons, employing combinatorial invariants such as counts of vertices, edges, and faces to analyze and incidence relations. This arises from the discrete nature of combinatorial counting versus the of continuous spaces, where phenomena like incommensurability highlight the irreducibility of continuous quantities to discrete units. Discretization processes bridge these domains by approximating smooth curves and manifolds with discrete representations, such as polygonal meshes or point clouds, to enable computational while preserving key geometric features. For curves, sample points are connected via piecewise linear segments, often refined through subdivision schemes to approach ; for surfaces, point clouds derived from scans are triangulated using algorithms like or the Ball-Pivoting method, converting continuous data into connected polygonal facets that approximate the original manifold's topology and metric properties. These approximations introduce finite resolution, allowing discrete methods to simulate continuous behaviors but at the cost of exact differentiability. Notable bridges between the fields include the χ=V−E+F\chi = V - E + F, where VV, EE, and FF denote vertices, edges, and faces, serving as a discrete topological invariant analogous to the continuous Gauss-Bonnet theorem, which relates total to χ\chi via integration over the surface. In discrete settings, variants of the Gauss-Bonnet theorem equate sums of local discrete curvatures—defined, for instance, as angle deficits at vertices or deviations from flatness in meshes—to multiples of χ\chi, mirroring how continuous integrates to 2πχ2\pi \chi for closed surfaces. Discrete curvature notions further extend this analogy, approximating continuous principal or mean curvatures through finite differences on meshes, such as cotangent-based Laplacians that converge to the smooth Laplace-Beltrami operator under mesh refinement. However, discretization imposes limitations, notably the loss of that engenders rigidity in discrete structures compared to the flexibility of continuous ones. In continuous geometry, deformations can occur smoothly along infinite , whereas discrete frameworks, like bar-joint structures, often exhibit combinatorial rigidity, where infinitesimal motions are constrained by incidence relations, preventing flexible deformations without breaking constraints. This rigidity manifests in phenomena like the generic rigidity of graphs in Rd\mathbb{R}^d, contrasting with the continuous case's allowance for non-trivial deformations in underconstrained manifolds. An illustrative example is optimization in , where discrete approaches restrict object positions to lattices or finite configurations, yielding exact but computationally intensive solutions via , while continuous formulations permit real-valued translations and rotations, enabling gradient-based optimization but introducing challenges like non-convexity and local minima not present in purely discrete variants. Polyhedra serve briefly as discrete analogs of curved surfaces in such contexts, approximating spheres or tori through faceted approximations.

Historical Development

Early Origins

The foundations of discrete geometry can be traced to , where early explorations of geometric structures laid the groundwork for combinatorial and discrete approaches. In his Elements (circa 300 BCE), systematically described the five regular polyhedra—tetrahedron, , , , and —proving their existence and properties as convex bodies bounded by congruent regular polygons, which anticipated later studies in polyhedral . also examined plane tilings through constructions of regular polygons and their arrangements, such as equilateral triangles and squares, establishing principles of that influenced discrete spatial divisions without continuous variation. During the , discrete geometric ideas gained prominence through influential conjectures and projective configurations. In 1611, proposed what became known as Kepler's conjecture, asserting that the face-centered cubic lattice achieves the densest packing of equal spheres in , with a density of π/(32)≈74.05%\pi / (3\sqrt{2}) \approx 74.05\%
Add your contribution
Related Hubs
User Avatar
No comments yet.