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
incidence properties
of it rather than its metric properties.
Most tiling
and coloring problems fit into this class,
but since they have their own sections of the junkyard, I omit them here.
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.
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?
Disjoint
triangles. Any 3n points in the plane can be partitioned into n
disjoint triangles. A. Bogomolny gives a simple proof and discusses
some generalizations.
Finding
the wood by the trees. Marc van Kreveld studies strategies by which
a blind man with a rope could map out a forest.
A
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.
Holyhedra.
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
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
PotW archive.
Integer distances.
Robert Israel gives a nice proof (originally due to Erdös) of the
fact that,
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.
K12
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).
Minimize
the slopes. How few different slopes can be formed by the lines
connecting 881 points?
From Stan Wagon's
PotW archive.
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.
Monge's
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
higher-dimensional spaces.
Plane
color. How big can the difference between the numbers of black and
white regions in a two-colored line arrangement?
From Stan Wagon's
PotW archive.
Polygon
power. How can one arrange six points to maximize the number of
simple polygons having all six points as vertices?
From Stan Wagon's
PotW archive.
See also Heidi Burgiel's
simple
n-gon counter.
Projective
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
O(nlog d).
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
straight-line edges:
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,
rectilinear
crossing constant, S. Finch, MathSoft, and
Calluna's pit,
Douglas Reay.
Rigid
regular r-gons.
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?
Rolling
polyhedra. Dave Boll investigates Hamiltonian paths on (duals of)
regular polyhedra.
The
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".)
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
tech. report.
Simple
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.
Solution
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
quant-ph/9905080 and
quant-ph/9911040
(on coloring just the rational points on a sphere), as well as this
four-dimensional construction
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.
Solving
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.)
Tangencies.
Animated compass and straightedge constructions of
various patterns of tangent circles.
Thrackles
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
my
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.
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).
This
talk abstract by Petr Lisonek (and paper in JCTA 77 (1997) 318-338)
describe some related results.
