Combinatorial geometry is a blending of principles from the areas of combinatorics and geometry. It deals with combinations and arrangements of geometric objects and with discrete properties of these objects. It is concerned with such topics as packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems. Combinatorial geometry includes aspects of topology, graph theory, number theory, and other disciplines.
Although combinatorial geometry was studied by classical mathematicians such as Euler and Kepler, many advances have been made since the middle of the 20th century. This topic was one which drew the interest of the late prolific mathematician Paul Erdős. The term "Combinatorial Geometry" was apparently first used in 1955 by H. Hadwiger (Hadwiger and Debrunner 1964).
David Eppstein's "Geometry Junkyard," a collection of geometry related web pages, has an extensive section devoted to combinatorial geometry topics, as well as a separate section for covering and packing.
A small sample of significant theorems and conjectures from this area are summarized in the following table.
theorem | description |
Borsuk's conjecture | covering a subset of of unit diameter using sets of diameter less than one |
Helly's theorem | common points in convex sets |
Kepler conjecture | optimum sphere packing |
Krasnoselskii's theorem | visibility of all points in a set |
Pick's theorem | area of a polygon on a grid with integer coordinates |
Sperner's lemma | labeling of triangle vertices |