Open Problems

These are open problems that I've encountered in the course of my research. Not surprisingly, almost all the problems are geometric in nature. A name in brackets is the first person to describe the problem to me; this may not be original source of the problem. If there's no name, either I thought of the problem myself (although I was certainly not the first to do so), or I just forgot who told me.

Problems in bold are described in more detail than the others, and are probably easier to understand without a lot of background knowledge.

If you have any ideas about how to solve these problems, or if you have any interesting open problems you'd like me to add, please let me know. I'd love to hear them!

30 Jul 2003: Complete or partial solutions for several of these problems have been discovered in the two years since I last updated this site. Over the next few weeks, I'm planning to add pointers to these new results, as well as descriptions of several new open problems. (Search for "soon" on this page.) Stay tuned!

Existence Problems: Does Object X exist?

• Unfolding convex polytopes [Joe O'Rourke and Komei Fukuda]
• Acute triangulation of the cube [Alper Üngör] (soon)

Combinatorial Problems: How complex is Object X?

• Degenerate facets of polytopes
• Faces of intricate polytopes
• Point-hyperplane incidences - update soon
• Union of intersecting unit balls - Solved!
• Line traversals of Delaunay triangulations [Nina Amenta] - Solved!
• Halving lines and k-sets
• Tangent pairs of (pseudo-)circles
• Medial surfaces of polyhedra and Voronoi diagrams of lines
• Forced convex subsets [The Erdös-Szekeres "happy end" problem]
• Maximum genus of an n-vertex 3d polyhedron (soon)
• Minimum spread of a neighborly triangulation (soon)
• Visibility complex of disjoint unit spheres (soon)

Algorithmic Problems: How fast can Problem X be solved?

• Minimum-area triangles
• Complex colinearities [David Eppstein]
• Extreme points
• A dynamic programming problem [David Eppstein]
• Shortest paths in line arrangements [Marc van Kreveld] - update soon
• Straight skeleton of a simple polygon [Franz Aurenhammer]
• Crashing motorcycles efficiently - update soon
• Klee's measure problem
• Generating random simple polygons
• Building convex polytopes [Erik Demaine and others]

Other People's Problems

• Some geometrical problems! from Olivier Devillers
• Lots of stuff from David Eppstein:
  • Open problems from The Geometry Junkyard
  • Open problems in mesh generation
  • Some of David's own research projects
• Unsolved Mathematics Problems collected by Steven Finch
• Bounty problems collected by Peter Kwok, including several problems first posed by Paul Erdõs [According to Ron Graham, rewards for Erdõs problems may not be honored now that Erdõs has died.]
• Open Problems on Discrete and Computational Geometry from Jorge Urrutia
• Combinatorial Geometry Open Problems contributed by Pavel Valtr to the DIMACS collection of Open Problems for Undergraduates

• Open problems from the 1996 AMS summer research conference "Discrete and Computational Geometry: Ten Years Later", some of which have already been solved
• Issue #8 of the computational geometry newsletter CG Tribune includes several open problems from the 1997 Dagstuhl computational geometry workshop.
• Electronic Scottish Café: Open problems from Ulam Quarterly: part 1 and part 2

Recommended Books

• Unsolved Problems in Geometry by Hallard Croft, Kenneth Falconer, and Richard Guy (Springer-Verlag, 1991)
• Old and New Unsolved Problems in Plane Geometry and Number Theory by Victor Klee and Stan Wagon (MAA, 1991).

We should try to love the questions themselves, like locked rooms and like books that are written in a very foreign tongue.

- Rainer Maria Rilke

Problem solving is hunting. It is savage pleasure, and we are born to it.

- Thomas Harris, The Silence of the Lambs

If you keep proving stuff that others have done, getting confidence, increasing the complexities of your solutions - for the fun of it - then one day you'll turn around and discover that nobody actually did that one! And that's the way to become a computer scientist.

- Richard Feynmann, Feynmann Lectures on Computation

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 09 Apr 2001