The Geometry Junkyard: Open Problems (original) (raw)

• Antipodes. Jim Propp asks whether the two farthest apart points, as measured by surface distance, on a symmetric convex body must be opposite each other on the body. Apparently this is open even for rectangular boxes.
• Bounded degree triangulation. Pankaj Agarwal and Sandeep Sen ask for triangulations of convex polytopes in which the vertex or edge degree is bounded by a constant or polylog.
• Centers of maximum matchings. Andy Fingerhut asks, given a maximum (not minimum) matching of six points in the Euclidean plane, whether there is a center point close to all matched edges (within distance a constant times the length of the edge). If so, it could be extended to more points via Helly's theorem. Apparently this is related to communication network design. I include a response I sent with a proof (of a constant worse than the one he wanted, but generalizing as well to bipartite matching).
• The chromatic number of the plane. Gordon Royle and Ilan Vardi summarize what's known about the famous open problem of how many colors are needed to color the plane so that no two points at a unit distance apart get the same color. See alsoanother article from Dave Rusin's known math pages.
  
• Covering points by rectangles. Stan Shebs discusses the problem of finding a minimum number of copies of a given rectangle that will cover all points in some set, and mentions an application to a computer strategy game. This is NP-hard, but I don't know how easy it is to approximate; most related work I know of is on optimizing the rectangle size for a cover by a fixed number of rectangles.
• Cube triangulation. Can one divide a cube into congruent and disjoint tetrahedra? And without the congruence assumption, how many higher dimensional simplices are needed to triangulate a hypercube? For more on this last problem, seeTriangulating an n-dimensional cube, S. Finch, MathSoft, andAsymptotically efficient triangulations of the d-cube, Orden and Santos.
  
• Embedding the hyperbolic plane in higher dimensional Euclidean spaces. D. Rusin summarizes what's known; the existence of an isometric immersion into R4 is apparently open.
• Geometric graph coloring problemsfrom "Graph Coloring Problems" by Jensen and Toft.
  
• Hermite's constants. Are certain values associated with dense lattice packings of spheres always rational? Part of Mathsoft'scollection of mathematical constants.
• 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).
• Mirrored room illumination. A summary by Christine Piatko of the old open problem of, given a polygon in which all sides are perfect mirrors, and a point source of light, whether the entire polygon will be lit up. The answer is no if smooth curves are allowed. See also Eric Weisstein's page on theIllumination Problem.
• Open problems:
  Demaine - Mitchell - O'Rourke open problems project
  From Jeff Erickson, Duke U.
  From Jorge Urrutia, U. Ottawa.
  From the 2nd MSI Worksh. on Computational Geometry.From SCG '98.
• Primes of a 14-omino. Michael Reid shows that a 3x6 rectangle with a 2x2 bite removed can tile a (much larger) rectangle. It is open whether it can do this using an odd number of copies.
• Prince Rupert's tetrahedra? One tetrahedron can be entirely contained in another, and yet have a larger sum of edge lengths. But how much larger? From Stan Wagon'sPotW archive.
• Pushing disks together. If unit disks move so their pairwise distances all decrease, does the area of their union also decrease?
• 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).
• Rational triangles. This well known problem asks whether there exists a triangle with the side lengths, medians, altitudes, and area all rational numbers. Randall Rathbun provides some "near misses" -- triangles in which most but not all of these quantities are irrational. See also Dan Asimov's question in geometry.puzzlesabout integer right-angled tetrahedra.
• Squares on a Jordan curve. Various people discuss the open problem of whether any Jordan curve in the plane contains four points forming the vertices of a square, and the related but not open problem of how to place a square table level on a hilltop. This is also in thegeometry.puzzles archive.
• Sums of square roots. A major bottleneck in proving NP-completeness for geometric problems is a mismatch between the real-number and Turing machine models of computation: one is good for geometric algorithms but bad for reductions, and the other vice versa. Specifically, it is not known on Turing machines how to quickly compare a sum of distances (square roots of integers) with an integer or other similar sums, so even (decision versions of) easy problems such as the minimum spanning tree are not known to be in NP. Joe O'Rourkediscusses an approach to this problem based on bounding the smallest difference between two such sums, so that one could know how precise an approximation to compute.
• Tiling problems. Collected at a problem session at Smith College, 1993, by Marjorie Senechal.
• Tiling the unit square with rectangles. Erich Friedman shows that the 5/6 by 5/6 square can always be tiled with 1/(k+1) by 1/(k+1) squares. Will all the 1/k by 1/(k+1) rectangles, for _k_>0, fit together in a unit square? Note that the sum of the rectangle areas is 1. Marc Paulhus can fit them into a square of side 1.000000001: "An algorithm for packing squares", J. Comb. Th. A 82 (1998) 147-157,MR1620857.
• Triangulations with many different areas. Eddie Grove asks for a function t(n) such that any n-vertex convex polygon has a triangulation with at least t(n) distinct triangle areas, and also discusses a special case in which the vertices are points in a lattice.
• Unfolding convex polyhedra. Catherine Schevon discusses whether it is always possible to cut a convex polyhedron's edges so its boundary unfolds into a simple planar polygon. Dave Rusin's known math pages includeanother article by J. O'Rourke on the same problem.
• Unsolved problems. Naoki Sato lists several conundrums from elementary geometry and number theory.

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-automaticallyfilteredfrom a common source file.