TOPICS

# Combinatorial Geometry

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

Borsuk's Conjecture, Helly's Theorem, Kepler Conjecture, Matroid, Pick's Theorem, Sperner's Lemma

Portions of this entry contributed by Len Goodman

## Explore with Wolfram|Alpha

More things to try:

## References

Croft, H. T.; Falconer, K. J.; and Guy, R. K. Unsolved Problems in Geometry. New York: Springer-Verlag, 1991.Eppstein, D. "Combinatorial Geometry." http://www.ics.uci.edu/~eppstein/junkyard/combinatorial.html.Eppstein, D. "Covering and Packing." http://www.ics.uci.edu/~eppstein/junkyard/cover.html.Erdős, P. Some Combinatorial Problems in Geometry. New York: Springer-Verlag, pp 46-53, 1980.Friedman, E. "Erich's Combinatorial Geometry Page." http://www.stetson.edu/~efriedma/comb.html.Hadwiger, H. and Debrunner, H. Combinatorial Geometry in the Plane. Holt, Rinehart & Winston 1964.Pach, J. and Agarwal, P. K. Combinatorial Geometry. New York: Wiley, 1995.

## Referenced on Wolfram|Alpha

Combinatorial Geometry

## Cite this as:

Goodman, Len and Weisstein, Eric W. "Combinatorial Geometry." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CombinatorialGeometry.html