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.

Borsuk's conjecturecovering a subset of R^d of unit diameter using d+1 sets of diameter less than one
Helly's theoremcommon points in convex sets
Kepler conjectureoptimum sphere packing
Krasnoselskii's theoremvisibility of all points in a set
Pick's theoremarea of a polygon on a grid with integer coordinates
Sperner's lemmalabeling of triangle vertices

See also

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


Croft, H. T.; Falconer, K. J.; and Guy, R. K. Unsolved Problems in Geometry. New York: Springer-Verlag, 1991.Eppstein, D. "Combinatorial Geometry.", D. "Covering and Packing."ős, P. Some Combinatorial Problems in Geometry. New York: Springer-Verlag, pp 46-53, 1980.Friedman, E. "Erich's Combinatorial Geometry Page.", 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.

Subject classifications