Combinatorial Geometry

• Colinear points on knots. Greg Kuperberg shows that a non-trivial knot or link in R³ 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?
  

• 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.

• Distinct point set with the same distance multiset. From K. S. Brown's Math Pages.

• An eight-point arrangement in which each perpendicular bisector passes through two other points. From Stan Wagon's PotW archive.

• 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 intersection points can you form from an n-line arrangement? Equivalently, how many opposite pairs of faces can an n-zone zonohedron have? 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(n^7/3) isosceles triangles; in three dimensions, Theta(n³) are possible (by generalizing the pentagon solution above). From Stan Wagon's PotW archive.

• HypArr, software for modeling and visualizing convex polyhedra and plane arrangements, now seems to be incorporated as a module in a larger Matlab library for multi-parametric analysis.

• Infinite families of simplicial arrangements.
  

• 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).

• The Kneser-Poulsen Conjecture. Bezdek and Connelly solve an old problem about pushing disks together.

• Layered graph drawing.
  

• Laying Track. The combinatorics and topology of Brio train layouts. From Ivars Peterson's MathTrek.

• Match sticks in the summer. Ivars Peterson discusses the graphs that can be formed by connecting vertices by non-crossing equal-length line segments.

• Max. non-adjacent vertices on 120-cell. Sci.math discussion on the size of the maximum independent set on this regular 4-polytope. Apparently it is known to be between 220 and 224 inclusive.

• 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.

• Popsicle stick bombs, lashings and weavings in the plane, F. Saliola.

• 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(n^{log 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 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 integers, by David and Ken Sloan, Dan Litchfield and Dave Goldenheim, Domingo Gómez Morín, and an 1811 textbook.

• 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".)

• Self-dual 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 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 R³ 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.)

• The Szilassi Polyhedron. This polyhedral torus, discovered by L. 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. Tom Ace has more images as well as a downloadable unfolded pattern for making your own copy. See also Dave Rusin's page on polyhedral tori with few vertices and Ivars' Peterson's MathTrek article.
  

• 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.

• 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 n²/2 + O(n). This 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 Object Server.
  

• Zonohedra and zonotopes. These centrally symmetric polyhedra provide another way of understanding the combinatorics of line arrangements.

From the Geometry Junkyard, computational and recreational geometry pointers.
Send email if you know of an appropriate page not listed here.
David Eppstein, Theory Group, ICS, UC Irvine.
Semi-automatically filtered from a common source file.