Nonrealizable Minimal Vertex Triangulations of Surfaces: Showing Nonrealizability Using Oriented Matroids and Satisfiability Solvers
Nonrealizable Minimal Vertex Triangulations of Surfaces: Showing Nonrealizability Using Oriented Matroids and Satisfiability Solvers
复制标题
曲面的不可实现最小顶点三角剖分：使用有向拟阵和可满足性求解器显示不可实现性
DOI：
--
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
L. Schewe
中科院分区：
文献类型：
--
作者：
L. Schewe
我们证明了亏格为6的闭连通可定向2-流形的极小顶点三角剖分不允许多面体嵌入到亏格3中。我们还提供了最小顶点三角形的封闭，连通，定向2流形的亏格5，不承认任何多面体嵌入的例子。纠正以前的文献中的错误，我们构建了第一个无限家庭的这种nonrealizable三角曲面。这些结果是通过将寻找合适的定向拟阵的问题转化为可满足性问题来实现的。该方法也可应用于其它几何可实现性问题，例如，对于多面体的面格。
We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in ℝ3. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. Correcting a previous error in the literature, we construct the first infinite family of such nonrealizable triangulations of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e.g., for face lattices of polytopes.