Discrete geometry and combinatorial geometry are branches of geometry

Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

 that study combinatorial

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

 properties and constructive methods of discrete

Discrete mathematics

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...

 geometric objects. Most questions in discrete geometry involve finite or discrete

Discrete space

In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...

 sets of basic geometric objects, such as point

Point (geometry)

In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...

s, lines

Line (geometry)

The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...

, planes, circle

Circle

A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....

s, sphere

Sphere

A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...

s, polygon

Polygon

In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...

s, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect

Intersection (set theory)

In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....

 one another, or how they may be arranged to cover a larger object.

Discrete geometry has large overlap with convex geometry

Convex geometry

Convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space.Convex sets occur naturally in many areas of mathematics: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbers, integral geometry, linear programming,...

 and computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, and is closely related to subjects such as finite geometry

Finite geometry

A finite geometry is any geometric system that has only a finite number of points.Euclidean geometry, for example, is not finite, because a Euclidean line contains infinitely many points, in fact as many points as there are real numbers...

, combinatorial optimization

Combinatorial optimization

In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...

, digital geometry

Digital geometry

Digital geometry deals with discrete 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

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...

, geometric graph theory

Geometric graph theory

In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...

, toric geometry

Toric geometry

In algebraic geometry, a toric variety or torus embedding is a normal variety containing an algebraic torus as a dense subset, such that the action of the torus on itself extends to the whole variety.-The toric variety of a fan:...

, and combinatorial topology

Combinatorial topology

In mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces were regarded as derived from combinatorial decompositions such as simplicial complexes...

.

History

Although polyhedra and tessellation

Tessellation

A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...

s have been studied for many years by people such as Kepler

Johannes Kepler

Johannes Kepler was a German mathematician, astronomer and astrologer. A key figure in the 17th century scientific revolution, he is best known for his eponymous laws of planetary motion, codified by later astronomers, based on his works Astronomia nova, Harmonices Mundi, and Epitome of Copernican...

 and Cauchy, modern discrete geometry has its origins in the late 19th century. Early topics studied were: the density of circle packing

Circle packing

In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that all circles touch another. The associated "packing density", η of an arrangement is the proportion of the surface covered by the circles...

s by Thue

Axel Thue

Axel Thue was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics....

, projective configurations by Reye and Steinitz

Ernst Steinitz

Ernst Steinitz was a German mathematician.- Biography :Steinitz was born in Laurahütte , Silesia, Germany , the son of Sigismund Steinitz, a Jewish coal merchant, and his wife Auguste Cohen; he had two brothers. He studied at the University of Breslau and the University of Berlin, receiving his Ph.D...

, the geometry of numbers

Geometry of numbers

In number theory, the geometry of numbers studies convex bodies and integer vectors in n-dimensional space. The geometry of numbers was initiated by ....

 by Minkowski, and map colourings by Tait, Heawood, and Hadwiger.

Topics in discrete geometry

• Polyhedra
  Polyhedron
  In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
  
   and polytope
  Polytope
  In elementary geometry, 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...
  
  s
  • Polyhedral combinatorics
    Polyhedral combinatorics
    Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher dimensional convex polytopes....
    
    
  • Lattice polytopes
    Convex lattice polytope
    A convex lattice polytope is a geometric object playing an important role in discrete geometry and combinatorial commutative algebra. It is a polytope in a Euclidean space Rn which is a convex hull of finitely many points in the integer lattice Zn ⊂ Rn...
    
    
  • Ehrhart polynomial
    Ehrhart polynomial
    In mathematics, an integral polytope has an associated Ehrhart polynomial which encodes the relationship between the volume of a polytope and the number of integer points the polytope contains...
    
    s
  • Pick's theorem
    Pick's theorem
    Given a simple polygon constructed on a grid of equal-distanced points such that all the polygon's vertices are grid points, Pick's theorem provides a simple formula for calculating the area A of this polygon in terms of the number i of lattice points in the interior located in the polygon and the...
    
    
  • Hirsch conjecture
    Hirsch conjecture
    In mathematical programming and polyhedral combinatorics, Hirsch's conjecture states that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a...
    
    

• Packings, coverings and tilings
  Tessellation
  A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
  
  
  • Circle packing
    Circle packing
    In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that all circles touch another. The associated "packing density", η of an arrangement is the proportion of the surface covered by the circles...
    
    s
  • Sphere packing
    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...
    
    s
  • Kepler conjecture
    Kepler conjecture
    The Kepler conjecture, named after the 17th-century German astronomer Johannes Kepler, is a mathematical conjecture about sphere packing in three-dimensional Euclidean space. It says that no arrangement of equally sized spheres filling space has a greater average density than that of the cubic...
    
    
  • Quasicrystal
    Quasicrystal
    A quasiperiodic crystal, or, in short, quasicrystal, is a structure that is ordered but not periodic. A quasicrystalline pattern can continuously fill all available space, but it lacks translational symmetry...
    
    s
  • Aperiodic tiling
    Aperiodic tiling
    An aperiodic tiling is a tiling obtained from an aperiodic set of tiles. Properly speaking, aperiodicity is a property of particular sets of tiles; any given finite tiling is either periodic or non-periodic...
    
    s
  • Periodic Graphs (Geometry)

• Structural rigidity
  Structural rigidity
  In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.-Definitions:...
  
   and flexibility
  • Cauchy's theorem
    Cauchy's theorem (geometry)
    Cauchy's theorem is a theorem in geometry, named after Augustin Cauchy. It states thatconvex polytopes in three dimensions with congruent corresponding faces must be congruent to each other...
    
    
  • Flexible polyhedra
    Flexible polyhedron
    In geometry, a flexible polyhedron is a polyhedral surface that allows continuous non-rigid deformations such that all faces remain rigid. The Cauchy rigidity theorem shows that in dimension 3 such a polyhedron cannot be convex .The first examples of flexible polyhedra, now called Bricard's...
    
    

• Incidence structure
  Incidence structure
  In mathematics, an incidence structure is a tripleC=.\,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 \in I,...
  
  s
  • Configurations
    Configuration (geometry)
    In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the same number of points.Although certain specific...
    
    
  • Line arrangements
    Arrangement of lines
    In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.-Definition:For any...
    
    
  • Hyperplane arrangements
    Arrangement of hyperplanes
    In geometry and combinatorics, an arrangement of hyperplanes is a finite set A of hyperplanes in a linear, affine, or projective space S....
    
    
  • Buildings

• Oriented matroid
  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...
  
  s

• Geometric graph theory
  Geometric graph theory
  In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...
  
  
  • Graph drawing
    Graph drawing
    Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
    
    
  • Polyhedral graph
    Polyhedral graph
    In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
    
    s
  • Voronoi diagram
    Voronoi diagram
    In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
    
    s and Delaunay triangulation
    Delaunay triangulation
    In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
    
    s

• Simplicial complex
  Simplicial complex
  In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...
  
  es

• Topological combinatorics
  Topological combinatorics
  The discipline of combinatorial topology used combinatorial concepts in topology and in the early 20th century this gradually turned into the field of algebraic topology....
  
  
  • Sperner's lemma
    Sperner's lemma
    In mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which follows from it. Sperner's lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors...
    
    
  • Regular maps
    Regular map (graph theory)
    In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold such as a sphere, torus, or Klein bottle into topological disks, such that every flag can be transformed into any other flag by a symmetry...
    
    

• Lattices
  Lattice (discrete subgroup)
  In Lie theory and related areas of mathematics, a lattice in a locally compact topological group is a discrete subgroup with the property that the quotient space has finite invariant measure...
  
   and discrete group
  Discrete group
  In mathematics, 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...
  
  s
  • Reflection group
    Reflection group
    In group theory and geometry, a reflection group is a discrete group which is generated by a set of reflections of a finite-dimensional Euclidean space. The symmetry group of a regular polytope or of a tiling of the Euclidean space by congruent copies of a regular polytope is necessarily a...
    
    s
  • Triangle group
    Triangle group
    In mathematics, a triangle group is a group that can be realized geometrically by sequences of reflections across the sides of a triangle. The triangle can be an ordinary Euclidean triangle, a triangle on the sphere, or a hyperbolic triangle...
    
    s
• Digital geometry
  Digital geometry
  Digital geometry deals with discrete 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
  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...
  
  

• Geometric set partitioning and transversals