TOPP: The Open Problems Project (original) (raw)

edited by Erik D. Demaine, Joseph S. B. Mitchell, Joseph O’Rourke

Introduction

This project originally aimed to record important open problems of interest to researchers in computational geometry and related fields. It commenced in 2001 with the publication of thirty problems in Computational Geometry Column 42 [MO01] (see Problems 1–30), and then grew to over 75 problems.

While we are no longer encouraging new problem submissions, we strongly encourage updates to existing problems, especially when those problems have been solved (completely or partially). Updates should be done in the form of a Github Pull Request; see the Github repository.

Each problem is assigned a unique number for citation purposes. Problem numbers also indicate the order in which the problems were entered. Each problem is classified as belonging to one or more categories.

The problems are also available as a single PDF file.

Numerical List of All Problems

To begin navigating through the open problems, you may select from a category of interest below, or view a list of all problems sorted numerically.

Categorized List of All Problems

Below, each category lists the problems that are classified under that category. Note that each problem may be classified under several categories.

arrangements:

art galleries:

coloring:

combinatorial geometry:

convex hulls:

data structures:

Delaunay triangulations:

dissections:

folding and unfolding:

geometric graphs:

graph drawing:

graphs:

linear programming:

lower bounds:

meshing:

minimum spanning tree:

numerical computations:

optimization:

packing:

partitioning:

partitioning.:

planar graphs:

point sets:

point sets.:

polygons:

polyhedra:

reconstruction:

robotics:

scheduling:

shortest paths:

simplification:

spanners:

stabbing:

traveling salesman:

triangulations:

visibility:

Voronoi diagrams:

Bibliography

[MO01]

J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.

Acknowledgments

Partially supported by NSF grants to the three editors.

This site is powered by Netlify.