HOME

TheInfoList



OR:

Discrete geometry and combinatorial geometry are branches of
geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
that study
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
properties and constructive methods of
discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory * Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit * Discrete group, ...
geometric objects. Most questions in discrete geometry involve finite or
discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory * Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit * Discrete group, ...
sets of basic geometric objects, such as points, lines, planes,
circle A circle is a shape consisting of all point (geometry), points in a plane (mathematics), plane that are at a given distance from a given point, the Centre (geometry), centre. The distance between any point of the circle and the centre is cal ...
s,
sphere A sphere (from Ancient Greek, Greek , ) is a surface (mathematics), surface analogous to the circle, a curve. In solid geometry, a sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
s,
polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
s, 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 Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
,
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. ...
, discrete differential geometry, geometric graph theory, toric geometry, and
combinatorial topology In mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces (for example the Betti numbers) were regarded as derived from combinatorial decompositions of spaces, such a ...
.


History

Polyhedra In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
and
tessellation A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety ...
s had been studied for many years by people such as
Kepler Johannes Kepler (27 December 1571 – 15 November 1630) was a German astronomer, mathematician, astrologer, natural philosopher and writer on music. He is a key figure in the 17th-century Scientific Revolution, best known for his laws of p ...
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 Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice (group), lattice in \mathbb R^n, and the study of these lattices provides fundam ...
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''.


Topics


Polyhedra and polytopes

A polytope is a geometric object with flat sides, which exists in any general number of dimensions. A
polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
is a polytope in two dimensions, a
polyhedron In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal Face (geometry), faces, straight Edge (geometry), edges and sharp corners or Vertex (geometry), vertices. The term "polyhedron" may refer ...
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
tessellation A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety ...
s), and
abstract polytope In mathematics, an abstract polytope is an algebraic partially ordered set which captures the dyadic property of a traditional polytope without specifying purely geometric properties such as points and lines. A geometric polytope is said to be ...
s. The following are some of the aspects of polytopes studied in discrete geometry: * Polyhedral combinatorics * Lattice polytopes * Ehrhart polynomials * Pick's theorem * Hirsch conjecture * Opaque set


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 In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...
. A sphere packing is an arrangement of non-overlapping
sphere A sphere (from Ancient Greek, Greek , ) is a surface (mathematics), surface analogous to the circle, a curve. In solid geometry, a sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
s within a containing space. The spheres considered are usually all of identical size, and the space is usually three-
dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...
al
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
. 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 Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, tessellations can be generalized to higher dimensions. Specific topics in this area include: * Circle packings *
Sphere packing In geometry, 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 p ...
s * Kepler conjecture *
Quasicrystal A quasiperiodicity, quasiperiodic crystal, or quasicrystal, is a structure that is Order and disorder (physics), ordered but not Bravais lattice, periodic. A quasicrystalline pattern can continuously fill all available space, but it lacks trans ...
s * Aperiodic tilings * Periodic graph *
Finite subdivision rule In mathematics, a finite subdivision rule is a recursive way of dividing a polygon or other two-dimensional shape into smaller and smaller pieces. Subdivision rules in a sense are generalizations of regular geometric fractals. Instead of repeati ...
s


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
hinge A hinge is a mechanical bearing that connects two solid objects, typically allowing only a limited angle of rotation between them. Two objects connected by an ideal hinge rotate relative to each other about a fixed axis of rotation, with all ...
s. Topics in this area include: * Cauchy's theorem * Flexible polyhedra


Incidence structures

Incidence structures generalize planes (such as
affine Affine may describe any of various topics concerned with connections or affinities. It may refer to: * Affine, a Affinity_(law)#Terminology, relative by marriage in law and anthropology * Affine cipher, a special case of the more general substi ...
, 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 :C=(P,L,I).\, where ''P'' is a set of "points", ''L'' is a set of "lines" and I \subseteq P \times L is the incidence relation. The elements of I are called flags. If :(p,l) \in I, we say that point ''p'' "lies on" line l. Topics in this area include: * Configurations * Line arrangements * Hyperplane arrangements * Buildings


Oriented matroids

An oriented matroid is a
mathematical structure In mathematics, a structure on a set (or on some sets) refers to providing or endowing it (or them) with certain additional features (e.g. an operation, relation, metric, or topology). Τhe additional features are attached or related to the ...
that abstracts the properties of directed graphs and of arrangements of vectors in a
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
over an
ordered field In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Basic examples of ordered fields are the rational numbers and the real numbers, both with their standard ord ...
(particularly for partially ordered vector spaces). In comparison, an ordinary (i.e., non-oriented)
matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
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''.


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 A skeleton is the structural frame that supports the body of most animals. There are several types of skeletons, including the exoskeleton, which is a rigid outer shell that holds up an organism's shape; the endoskeleton, a rigid internal fra ...
of a
polyhedron In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal Face (geometry), faces, straight Edge (geometry), edges and sharp corners or Vertex (geometry), vertices. The term "polyhedron" may refer ...
or
polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
, unit disk graphs, and visibility graphs. Topics in this area include: * Graph drawing * Polyhedral graphs * Random geometric graphs * Voronoi diagrams and
Delaunay triangulation In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
s


Simplicial complexes

A simplicial complex is a
topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...
of a certain kind, constructed by "gluing together" points,
line segment In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
s,
triangle A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called ''vertices'', are zero-dimensional points while the sides connecting them, also called ''edges'', are one-dimension ...
s, and their Simplex, ''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 Vietoris–Rips_complex, 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 graph, 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: *Sperner's lemma *Regular map (graph theory), Regular maps


Lattices and discrete groups

A discrete group is a Group (mathematics), 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 real numbers, reals, R (with the standard Metric space, 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 (topology), 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 (group), lattice, and both the algebraic structure of lattices and the geometry of the totality of all lattices are relatively well understood. Deep results of Armand Borel, Borel, Harish-Chandra, George Mostow, Mostow, Tsuneo Tamagawa, Tamagawa, M. S. Raghunathan, Grigory Margulis, Margulis, Robert Zimmer (mathematician), Zimmer obtained from the 1950s through the 1970s provided examples and generalized much of the theory to the setting of nilpotent group, nilpotent Lie groups and semisimple algebraic groups over a local field. In the 1990s, Hyman Bass, Bass and Alexander Lubotzky, Lubotzky initiated the study of ''tree lattices'', which remains an active research area. Topics in this area include: *Reflection groups *Triangle groups


Digital geometry

Digital geometry deals with discrete space, discrete sets (usually discrete point sets) considered to be digitizing, digitized scale model, models or images of objects of the 2D or 3D
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
. Simply put, digitizing is replacing an object by a discrete set of its points. The images we see on the TV screen, the raster graphics, raster display of a computer, or in newspapers are in fact Digital data, digital images. Its main application areas are computer graphics and image analysis.Se
Li Chen, Digital and discrete geometry: Theory and Algorithms, Springer, 2014.
/ref>


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
polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
s, 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 calculus *Discrete Morse theory *Topological combinatorics *Spectral shape analysis *Analysis on fractals


See also

*''Discrete and Computational Geometry'' (journal) *Discrete mathematics * Paul Erdős


Notes


References

* * * * * * * * * * {{authority control Discrete geometry,