This is a difficult topic to define precisely
without including all of discrete and computational geometry.
What I mean by "combinatorial geometry" consists of
problems in which one starts with a geometric figure
(say a polytope) but then considers abstract
of it rather than its metric properties.
and coloring problems fit into this class,
but since they have their own sections of the junkyard, I omit them here.
- Colinear points on knots.
shows that a non-trivial knot or link in R3
necessarily has four colinear points.
- A Counterexample to Borsuk's Conjecture, J. Kahn and G. Kalai,
Bull. AMS 29 (1993). Partitioning certain high-dimensional polytopes
into pieces with smaller diameter requires a number of pieces
exponential in the dimension.
- Delaunay triangulation and points of
intersection of lines. Tom McGlynn asks whether the DT of a line
arrangement's vertices must respect the lines; H. K. Ruud shows that the
answer is no.
- Diamond theory.
Steven Cullinane studies the symmetries of the shapes formed by
splitting each square of a grid into dark and light triangles.
- Dictionary of Combinatorics,
Joe Fields, U. Illinois at Chicago.
- Dilation-free planar graphs.
How can you arrange n points so that the set of all lines between them
forms a planar graph with no extra vertices?
triangles. Any 3n points in the plane can be partitioned into n
disjoint triangles. A. Bogomolny gives a simple proof and discusses
- Distinct point set with the same distance multiset.
From K. S. Brown's Math Pages.
eight-point arrangement in which each perpendicular bisector passes
through two other points.
From Stan Wagon's
the wood by the trees. Marc van Kreveld studies strategies by which
a blind man with a rope could map out a forest.
Geometrical Picturebook of finite and combinatorial geometries,
B. Polster, to be published by Springer.
- Grid subgraphs.
Jan Kristian Haugland looks for sets of lattice points that induce
graphs with high degree but no short cycles.
Jade Vinson solves a question of John Conway on the existence of
finite polyhedra all of whose faces have holes in them
(the Menger sponge provides
an infinite example).
- How many intersection points
can you form from an n-line arrangement?
Equivalently, how many opposite pairs of faces can an n-zone
It must be a number between n-1 and n(n-1)/2,
but not all of those values are possible.
- How many
points can one find in three-dimensional space so that all triangles
are equilateral or isosceles?
One eight-point solution is formed by placing three points
on the axis of a regular pentagon.
This problem seems related to the fact that
any planar point set forms O(n7/3)
isosceles triangles; in three dimensions, Theta(n3) are possible
(by generalizing the pentagon solution above). From Stan Wagon's
software for modeling and visualizing convex polyhedra and plane
now seems to be incorporated as a module in a larger
Matlab library for multi-parametric analysis.
families of simplicial arrangements.
- Integer distances.
Robert Israel gives a nice proof (originally due to Erdös) of the
in any non-colinear planar point set in which all distances
are integers, there are only finitely many points.
Infinite sets of points with rational distances are known,
from which arbitrarily large finite sets of points with integer
distances can be constructed; however it is open whether there are even
seven points at integer distances in general position
(no three in a line and no four on a circle).
- Interconnection Trees. Java minimum spanning tree implementation, Joe Ganley, Virginia.
- Intersecting cube diagonals.
Mark McConnell asks for a proof that, if a convex polyhedron
combinatorially equivalent to a cube has three of the four
body diagonals meeting at a point, then the fourth one meets
there as well. There is apparently some connection to toric varieties.
on G6. Carlo Séquin investigates how to draw a 12-vertex
complete graph as symmetrically as possible on a six-handle surface
(the minimum genus surface on which it can be drawn without crossings).
Bezdek and Connelly solve an old problem about pushing disks together.
- Layered graph drawing.
Track. The combinatorics and topology of Brio train layouts. From
Ivars Peterson's MathTrek.
sticks in the summer. Ivars Peterson discusses the graphs
that can be formed by connecting vertices by non-crossing equal-length
non-adjacent vertices on 120-cell. Sci.math discussion on the size
of the maximum independent set on this regular 4-polytope.
it is known to be between 220 and 224 inclusive.
the slopes. How few different slopes can be formed by the lines
connecting 881 points?
From Stan Wagon's
- Models of Small Geometries.
Burkard Polster draws diagrams of combinatorial configurations such as the
Fano plane and Desargues' theorem (shown below) in an attempt to capture the
mathematical beauty of these geometries.
theorem and Desargues' theorem, identified.
Thomas Banchoff relates these two results,
on colinearity of intersections of external tangents to disjoint circles,
and of intersections of sides of perspective triangles, respectively.
He also describes generalizations to higher dimensional spheres.
- Odd squared distances. Warren Smith considers point sets
for which the square of each interpoint distance is an odd integer.
Clearly one can always do this with an appropriately scaled regular simplex;
Warren shows that one can squeeze just one more point in,
iff the dimension is 2 (mod 4).
Moshe Rosenfeld has published a related paper in Geombinatorics
(vol. 5, 1996, pp. 156-159).
- Packings in Grassmannian spaces, N. Sloane, AT&T.
How to arrange lines, planes, and other low-dimensional spaces into
color. How big can the difference between the numbers of black and
white regions in a two-colored line arrangement?
From Stan Wagon's
power. How can one arrange six points to maximize the number of
simple polygons having all six points as vertices?
From Stan Wagon's
See also Heidi Burgiel's
stick bombs, lashings and weavings in the plane, F. Saliola.
Duality. This Java applet by F. Henle of Dartmouth demonstrates
three different incidence-preserving translations from points to lines
and vice versa in the projective plane.
- Proofs of Euler's Formula.
V-E+F=2, where V, E, and F are respectively the numbers of
vertices, edges, and faces of a convex polyhedron.
- A quasi-polynomial bound for the diameter of graphs of polyhedra,
G. Kalai and D. Kleitman, Bull. AMS 26 (1992). A famous open conjecture in polyhedral
combinatorics (with applications to e.g. the simplex method in linear
programming) states that any two vertices of an n-face polytope are
linked by a chain of O(n) edges. This paper gives the weaker bound
- Random spherical arc crossings.
Bill Taylor and Tal Kubo prove that if one takes two random geodesics
on the sphere, the probability that they cross is 1/8.
This seems closely related a famous problem on the probability
of choosing a convex quadrilateral from a planar distribution.
The minimum (over all possible distributions) of this probability
also turns out to solve a seemingly unrelated combinatorial
geometry problem, on the minimum
number of crossings possible in a drawing of the complete graph with
see also "The
rectilinear crossing number of a complete graph
and Sylvester's four point problem of geometric probability",
E. Scheinerman and H. Wilf, Amer. Math. Monthly 101 (1994) 939-943,
crossing constant, S. Finch, MathSoft, and
Erich Friedman asks how many unit-length bars are needed in a
bar-and-joint linkage network to make a unit regular polygon rigid.
What if the polygon can have non-unit-length edges?
polyhedra. Dave Boll investigates Hamiltonian paths on (duals of)
- The rotating caliper graph.
A thrackle used in "Average Case Analysis of Dynamic Geometric Optimization"
for maintaining the width and diameter of a point set.
- Ruler and compass construction of the Fibonacci numbers and other
David and Ken Sloan, Dan Litchfield and Dave Goldenheim,
Domingo Gómez Morín,
and an 1811 textbook.
Schläfli Double Six.
A lovely photo-essay of models of this configuration,
in which twelve lines each meet five of thirty points.
Unfortunately only the first page seems to be archived...
(This site also referred to
related configurations involving 27 lines meeting either 45 or
135 points, but didn't describe any mathematical details.
For further descriptions of all of these, see Hilbert and
Cohn-Vossen's "Geometry and the Imagination".)
maps, Don McConnell.
- Sets of points with many halving lines.
Coordinates for arrangements of 14, 16, and 18 points for which
many of the lines determined by two points split the remaining points
exactly in half. From my 1992
polygonizations. Erik Demaine explores the question of how many
different non-crossing traveling salesman tours an n-point set can have.
- Simplex/hyperplane intersection.
Doug Zare nicely summarizes the shapes that can arise on intersecting
a simplex with a hyperplane: if there are p points on the hyperplane,
m on one side, and n on the other side, the shape is
(a projective transformation of)
a p-iterated cone over the product of m-1 and n-1 dimensional simplices.
- Six-regular toroid.
Mike Paterson asks whether it is possible to make a torus-shaped polyhedron
in which exactly six equilateral triangles meet at each vertex.
- Skewered lines.
Jim Buddenhagen notes that four lines in general position in R3
have exactly two lines crossing them all, and asks how this generalizes
to higher dimensions.
to problem 10769. Apparently problems of coloring the points of a
sphere so that orthogonal points have different colors (or so that each
set of coordinate basis vectors has multiple colors) has some relevance
to quantum mechanics; see also papers
(on coloring just the rational points on a sphere), as well as this
of an odd number of basis sets in which each vector appears an even
number of times, showing that one can't color the points on a
four-sphere so that each basis set has exactly one black point.
the Petersen Graph Zome Challenge.
David MacMahon discovers that there is no way to make a
non-self-intersecting peterson graph with Zome tool.
Includes VRML illustrations.
- Sylvester's theorem.
This states that any finite non-colinear point set has
a line containing only two points (equivalently, every zonohedron has a
quadrilateral face). Michael Larsen, Tim Chow, and Noam
Elkies discuss two proofs and a complex-number generalization.
(They omit the very simple generalization from Euler's
formula: every convex polyhedron has a face of degree at most five.)
- The Szilassi Polyhedron.
This polyhedral torus, discovered by
Szilassi, has seven hexagonal faces, all adjacent to each other.
It has an axis of 180-degree symmetry; three pairs of faces are congruent
leaving one unpaired hexagon that is itself symmetric.
Ace has more images as well as a downloadable unfolded pattern
for making your own copy.
See also Dave Rusin's page on
tori with few vertices and
Peterson's MathTrek article.
Animated compass and straightedge constructions of
various patterns of tangent circles.
are graphs embedded as a set of curves in the plane that cross each
other exactly once; Conway has conjectured that an n-vertex
thrackle has at most n edges.
Stephan Wehner describes what is known about thrackles.
- Triangles and squares.
Slides from a talk I gave relating a simple 2d puzzle, Escher's drawings
of 3d polyhedra, and the combinatorics of 4d polytopes, via angles in
hyperbolic space. Warning: very large file (~8Mb).
For more technical details see
paper with Kuperberg and Ziegler.
- Triangulation numbers. These classify the geometric structure of
viruses. Many viruses are shaped as simplicial polyhedra consisting of 12
symmetrically placed degree five vertices and more degree six vertices;
the number represents the distance between degree five vertices.
- 27 lines on the Clebsch cubic, Matthias Weber.
- Two-distance sets.
Timothy Murphy and others discuss how many points one can have
in an n-dimensional set, so that there are only two distinct
interpoint distances. The correct answer turns out to
be n2/2 + O(n).
talk abstract by Petr Lisonek (and paper in JCTA 77 (1997) 318-338)
describe some related results.
- A Venn diagram
made from five congruent ellipses. From F. Ruskey's Combinatorial
- Zonohedra and zonotopes. These centrally
symmetric polyhedra provide another way of understanding the
combinatorics of line arrangements.
From the Geometry Junkyard,
and recreational geometry pointers.
Send email if you
know of an appropriate page not listed here.
from a common source file.