The Open Problems Project

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:

• 3-Colorability of Arrangements of Great Circles (Problem 44)

art galleries:

• Vertex \pi-Floodlights (Problem 23)

coloring:

• 3-Colorability of Arrangements of Great Circles (Problem 44)

combinatorial geometry:

• k-sets (Problem 7)

• Binary Space Partition Size (Problem 14)

• Chromatic Number of the Plane (Problem 57)

• Counting Polyominoes (Problem 37)

• Distances among Point Sets in \R^2 and \R^3 (Problem 39)

• Extending Pseudosegment Arrangements by Subdivision (Problem 34)

• Lines Tangent to Four Unit Balls (Problem 61)

• Monochromatic Triangles (Problem 58)

• Pushing Disks Together (Problem 18)

• Rolling a Die over a Labeled Board (Problem 68)

• Slicing Axes-Parallel Rectangles (Problem 74)

• The Number of Pointed Pseudotriangulations (Problem 40)

• Thrackles (Problem 30)

• Union of Fat Objects in 3D (Problem 4)

• Vertical Decompositions in \R^d (Problem 19)

convex hulls:

• Dynamic Planar Convex Hull (Problem 12)

• Dynamic Planar Nearest Neighbors (Problem 63)

• Inplace Convex Hull of a Simple Polygonal Chain (Problem 36)

• Output-sensitive Convex Hull in \R^d (Problem 15)

data structures:

• Binary Space Partition Size (Problem 14)

• Dynamic Planar Convex Hull (Problem 12)

• Dynamic Planar Nearest Neighbors (Problem 63)

• Point Location in 3D Subdivision (Problem 13)

Delaunay triangulations:

• Flip Graph Connectivity in 3D (Problem 28)

• Stretch-Factor for Points in Convex Position (Problem 71)

• Voronoi Diagram of Moving Points (Problem 2)

dissections:

• Congruent Partitions of Polygons (Problem 73)

folding and unfolding:

• Edge-Unfolding Convex Polyhedra (Problem 9)

• Edge-Unfolding Polycubes (Problem 64)

• General Unfoldings of Nonconvex Polyhedra (Problem 43)

• Vertex-Unfolding Polyhedra (Problem 42)

• Volume Maximizing Convex Shape (Problem 62)

geometric graphs:

• Edge-Coloring Geometric Graphs (Problem 75)

• Thrackles (Problem 30)

• Yao-Yao Graph a Spanner? (Problem 70)

graph drawing:

• 3D Minimum-Bend Orthogonal Graph Drawings (Problem 46)

• Isoceles Planar Graph Drawing (Problem 69)

• Linear-Volume 3D Grid Drawings of Planar Graphs (Problem 51)

• Queue-Number of Planar Graphs (Problem 52)

• Smallest Universal Set of Points for Planar Graphs (Problem 45)

• Thrackles (Problem 30)

graphs:

• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)

• Smallest Universal Set of Points for Planar Graphs (Problem 45)

• Thrackles (Problem 30)

• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

linear programming:

• Linear Programming: Strongly Polynomial? (Problem 8)

lower bounds:

• 3SUM Hard Problems (Problem 11)

• Sorting X+Y (Pairwise Sums) (Problem 41)

meshing:

• Hexahedral Meshing (Problem 27)

• Most Circular Partition of a Square (Problem 59)

minimum spanning tree:

• Bounded-Degree Minimum Euclidean Spanning Tree (Problem 48)

• Euclidean Minimum Spanning Tree (Problem 5)

numerical computations:

• Sum of Square Roots (Problem 33)

optimization:

• Bounded-Degree Minimum Euclidean Spanning Tree (Problem 48)

• Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots (Problem 35)

• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)

• Packing Unit Squares in a Simple Polygon (Problem 56)

• Pallet Loading (Problem 55)

• Planar Euclidean Maximum TSP (Problem 49)

• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

packing:

• Most Circular Partition of a Square (Problem 59)

• Packing Unit Squares in a Simple Polygon (Problem 56)

• Pallet Loading (Problem 55)

• Rectangling a Rectangle (Problem 78)

partitioning:

• Congruent Partitions of Polygons (Problem 73)

• Fair Partitioning of Convex Polygons (Problem 67)

partitioning.:

• Rectangling a Rectangle (Problem 78)

planar graphs:

• Bar-Magnet Polyhedra (Problem 32)

• Isoceles Planar Graph Drawing (Problem 69)

• Pointed Spanning Trees in Triangulations (Problem 50)

point sets:

• k-sets (Problem 7)

• Bounded-Degree Minimum Euclidean Spanning Tree (Problem 48)

• Magic Configurations (Problem 65)

• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)

• Planar Euclidean Maximum TSP (Problem 49)

• Simple Polygonalizations (Problem 16)

• Smallest Universal Set of Points for Planar Graphs (Problem 45)

• Surface Reconstruction (Problem 26)

• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

point sets.:

• Reflexivity of Point Sets (Problem 66)

polygons:

• Congruent Partitions of Polygons (Problem 73)

• Fair Partitioning of Convex Polygons (Problem 67)

• Hinged Dissections (Problem 47)

• Reflexivity of Point Sets (Problem 66)

• Simple Polygonalizations (Problem 16)

• Transforming Polygons via Vertex-Centroid Moves (Problem 60)

polyhedra:

• 3-Colorability of Arrangements of Great Circles (Problem 44)

• Bar-Magnet Polyhedra (Problem 32)

• Edge-Unfolding Convex Polyhedra (Problem 9)

• Edge-Unfolding Polycubes (Problem 64)

• Equiprojective Polyhedra (Problem 76)

• General Unfoldings of Nonconvex Polyhedra (Problem 43)

• Hamiltonian Tetrahedralizations (Problem 29)

• Polyhedron with Regular Pentagon Faces (Problem 72)

• Vertex-Unfolding Polyhedra (Problem 42)

• Zipper Unfoldings of Convex Polyhedra (Problem 77)

reconstruction:

• Surface Reconstruction (Problem 26)

robotics:

• Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots (Problem 35)

scheduling:

• Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots (Problem 35)

shortest paths:

• Euclidean Minimum Spanning Tree (Problem 5)

• Minimum Euclidean Matching in 2D (Problem 6)

• Minimum-Link Path in 2D (Problem 22)

• Shortest Paths among Obstacles in 2D (Problem 21)

simplification:

• Polygonal Curve Simplification (Problem 24)

• Polyhedral Surface Approximation (Problem 25)

spanners:

• Stretch-Factor for Points in Convex Position (Problem 71)

• Yao-Yao Graph a Spanner? (Problem 70)

stabbing:

• Minimum Stabbing Spanning Tree (Problem 20)

traveling salesman:

• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)

• Planar Euclidean Maximum TSP (Problem 49)

• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

triangulations:

• Compatible Triangulations (Problem 38)

• Flip Graph Connectivity in 3D (Problem 28)

• Hamiltonian Tetrahedralizations (Problem 29)

• Minimum Weight Triangulation (Problem 1)

• Pointed Spanning Trees in Triangulations (Problem 50)

• Simple Linear-Time Polygon Triangulation (Problem 10)

• The Number of Pointed Pseudotriangulations (Problem 40)

visibility:

• Trapping Light Rays with Segment Mirrors (Problem 31)

• Vertex \pi-Floodlights (Problem 23)

• Visibility Graph Recognition (Problem 17)

Voronoi diagrams:

• Dynamic Planar Nearest Neighbors (Problem 63)

• Voronoi Diagram of Lines in 3D (Problem 3)

• Voronoi Diagram of Moving Points (Problem 2)

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.