计算几何中的开放问题

编辑：Erik D. Demaine, Joseph S. B. Mitchell, Joseph O’Rourke

介绍

本项目最初旨在记录计算几何及相关领域研究人员感兴趣的重要开放问题。它始于 2001 年，在 Computational Geometry Column 42 [MO01] 中发布了 30 个问题（参见问题 1–30），随后扩展到超过 75 个问题。

虽然我们不再鼓励提交新的问题，但我们强烈建议更新现有问题，特别是当这些问题已经（全部或部分）解决时。更新应以 GitHub Pull Request 的形式进行；请参阅 GitHub 仓库：Github repository。

每个问题都被分配一个唯一的编号，用于引用。问题编号也表示问题的输入顺序。每个问题都被分类为属于一个或多个类别。

这些问题也可以作为单个 PDF 文件获取。

所有问题的数字列表

要开始浏览这些开放问题，您可以从下面选择一个感兴趣的类别，或者查看按数字排序的所有问题列表。

所有问题的分类列表

下面，每个类别都列出了该类别下的问题。请注意，每个问题可能被归类为多个类别。

arrangements:

• Great Circles 排列的 3-可着色性 (问题 44)

art galleries:

• 顶点 π\piπ-Floodlights (问题 23)

coloring:

• Great Circles 排列的 3-可着色性 (问题 44)

combinatorial geometry:

• kkk-sets (问题 7)
• Binary Space Partition Size (问题 14)
• 平面的色数 (问题 57)
• Counting Polyominoes (问题 37)
• R2\R^2R2 和 R3\R^3R3 中点集的距离 (问题 39)
• 通过细分扩展伪线段排列 (问题 34)
• 与四个单位球相切的线 (问题 61)
• Monochromatic Triangles (问题 58)
• 推动圆盘靠拢 (问题 18)
• 在标记的板上滚动骰子 (问题 68)
• Slicing Axes-Parallel Rectangles (问题 74)
• 尖伪三角剖分的数量 (问题 40)
• Thrackles (问题 30)
• 3D 中胖对象的并集 (问题 4)
• Rd\R^dRd 中的垂直分解 (问题 19)

convex hulls:

• Dynamic Planar Convex Hull (问题 12)
• Dynamic Planar Nearest Neighbors (问题 63)
• 简单多边形链的 Inplace Convex Hull (问题 36)
• Rd\R^dRd 中的输出敏感凸包 (问题 15)

data structures:

• Binary Space Partition Size (问题 14)
• Dynamic Planar Convex Hull (问题 12)
• Dynamic Planar Nearest Neighbors (问题 63)
• 3D 细分中的点定位 (问题 13)

Delaunay triangulations:

• 3D 中的 Flip Graph 连通性 (问题 28)
• 凸位置中点的拉伸因子 (问题 71)
• 移动点的 Voronoi 图 (问题 2)

dissections:

• 多边形的同余分割 (问题 73)

folding and unfolding:

• 凸多面体的边缘展开 (问题 9)
• 多立方体的边缘展开 (问题 64)
• 非凸多面体的一般展开 (问题 43)
• 多面体的顶点展开 (问题 42)
• 体积最大化的凸形状 (问题 62)

geometric graphs:

• 几何图的边着色 (问题 75)
• Thrackles (问题 30)
• Yao-Yao Graph 是 Spanner 吗？ (问题 70)

graph drawing:

• 3D 最小弯曲正交图绘制 (问题 46)
• 等腰平面图绘制 (问题 69)
• 平面图的线性体积 3D 网格绘制 (问题 51)
• 平面图的队列数 (问题 52)
• 平面图的最小通用点集 (问题 45)
• Thrackles (问题 30)

graphs:

• 平面网格图中的最小转弯循环覆盖 (问题 53)
• 平面图的最小通用点集 (问题 45)
• Thrackles (问题 30)
• 实体网格图中的旅行商问题 (问题 54)

linear programming:

• 线性规划：强多项式？ (问题 8)

lower bounds:

• 3SUM 难题 (问题 11)
• 排序 X+YX+YX+Y (成对和) (问题 41)

meshing:

• 六面体网格划分 (问题 27)
• 正方形的最圆划分 (问题 59)

minimum spanning tree:

• 有界度最小欧几里德生成树 (问题 48)
• 欧几里德最小生成树 (问题 5)

numerical computations:

• 平方根之和 (问题 33)

optimization:

• 有界度最小欧几里德生成树 (问题 48)
• Freeze-Tag：唤醒机器人群的最佳策略 (问题 35)
• 平面网格图中的最小转弯循环覆盖 (问题 53)
• 在简单多边形中填充单位正方形 (问题 56)
• Pallet Loading (问题 55)
• 平面欧几里德最大 TSP (问题 49)
• 实体网格图中的旅行商问题 (问题 54)

packing:

• 正方形的最圆划分 (问题 59)
• 在简单多边形中填充单位正方形 (问题 56)
• Pallet Loading (问题 55)
• 将矩形变为矩形 (问题 78)

partitioning:

• 多边形的同余分割 (问题 73)
• 凸多边形的公平分割 (问题 67)

partitioning.:

• 将矩形变为矩形 (问题 78)

planar graphs:

• Bar-Magnet Polyhedra (问题 32)
• 等腰平面图绘制 (问题 69)
• 三角剖分中的尖生成树 (问题 50)

point sets:

• kkk-sets (问题 7)
• 有界度最小欧几里德生成树 (问题 48)
• Magic Configurations (问题 65)
• 平面网格图中的最小转弯循环覆盖 (问题 53)
• 平面欧几里德最大 TSP (问题 49)
• Simple Polygonalizations (问题 16)
• 平面图的最小通用点集 (问题 45)
• 曲面重建 (问题 26)
• 实体网格图中的旅行商问题 (问题 54)

point sets.:

• 点集的自反性 (问题 66)

polygons:

• 多边形的同余分割 (问题 73)
• 凸多边形的公平分割 (问题 67)
• 铰接解剖 (问题 47)
• 点集的自反性 (问题 66)
• Simple Polygonalizations (问题 16)
• 通过顶点-质心移动变换多边形 (问题 60)

polyhedra:

• Great Circles 排列的 3-可着色性 (问题 44)
• Bar-Magnet Polyhedra (问题 32)
• 凸多面体的边缘展开 (问题 9)
• 多立方体的边缘展开 (问题 64)
• Equiprojective Polyhedra (问题 76)
• 非凸多面体的一般展开 (问题 43)
• 哈密顿四面体化 (问题 29)
• 具有规则五边形面的多面体 (问题 72)
• 多面体的顶点展开 (问题 42)
• 凸多面体的 Zipper 展开 (问题 77)

reconstruction:

• 曲面重建 (问题 26)

robotics:

• Freeze-Tag：唤醒机器人群的最佳策略 (问题 35)

scheduling:

• Freeze-Tag：唤醒机器人群的最佳策略 (问题 35)

shortest paths:

• 欧几里德最小生成树 (问题 5)
• 2D 中的最小欧几里德匹配 (问题 6)
• 2D 中的最小链接路径 (问题 22)
• 2D 中障碍物之间的最短路径 (问题 21)

simplification:

• 多边形曲线简化 (问题 24)
• 多面体曲面逼近 (问题 25)

spanners:

• 凸位置中点的拉伸因子 (问题 71)
• Yao-Yao Graph 是 Spanner 吗？ (问题 70)

stabbing:

• 最小刺穿生成树 (问题 20)

traveling salesman:

• 平面网格图中的最小转弯循环覆盖 (问题 53)
• 平面欧几里德最大 TSP (问题 49)
• 实体网格图中的旅行商问题 (问题 54)

triangulations:

• 兼容的三角剖分 (问题 38)
• 3D 中的 Flip Graph 连通性 (问题 28)
• 哈密顿四面体化 (问题 29)
• 最小权重三角剖分 (问题 1)
• 三角剖分中的尖生成树 (问题 50)
• 简单线性时间多边形三角剖分 (问题 10)
• 尖伪三角剖分的数量 (问题 40)

visibility:

• 用线段镜捕获光线 (问题 31)
• 顶点 π\piπ-Floodlights (问题 23)
• 可见性图识别 (问题 17)

Voronoi diagrams:

• Dynamic Planar Nearest Neighbors (问题 63)
• 3D 中线的 Voronoi 图 (问题 3)
• 移动点的 Voronoi 图 (问题 2)

参考文献

[MO01]

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

致谢

部分由 NSF 资助授予三位编辑。 本网站由 Netlify 驱动。