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 also
another 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.
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.
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 the
Illumination
Problem.
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's
PotW 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.puzzles
about 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 the
geometry.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'Rourke
discusses 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 include
another article by J. O'Rourke on the same problem.
Unsolved
problems. Naoki Sato lists several conundrums from elementary
geometry and number theory.
