论文标题
部分可观测时空混沌系统的无模型预测
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles
论文作者
论文摘要
折纸数学的基本结果是川崎和贾斯汀对未分配的单个crease折痕图案（每个折痕都可以折叠山或山谷）对平坦可折叠性的简单，有效的表征。后来将此结果推广到材料锥中，其中粘在单个顶点的角度可能不会总计$ 360^\ circ $。在这里，我们将这些结果推广到材料形成复合物（而不是歧管）时，因此将角度粘在任意平面图的结构中（而不是循环）的结构中的单个顶点。像较早的特征一样，我们需要所有的折痕才能折叠山或山谷，而不会保持平坦。否则，已知该问题是NP完整的（对于扁平材料而言弱，对于复合物而言）。等效地，我们有效地表征了哪些具有规定边缘长度的组合嵌入的平面图可以平坦地折叠，当所有角度必须是山地或山谷（不展开的平坦）时。我们的算法以$ o（n \ log^3 n）$时间运行，改进了$ o（n^2 \ log n）$的先前最佳算法。
A foundational result in origami mathematics is Kawasaki and Justin's simple, efficient characterization of flat foldability for unassigned single-vertex crease patterns (where each crease can fold mountain or valley) on flat material. This result was later generalized to cones of material, where the angles glued at the single vertex may not sum to $360^\circ$. Here we generalize these results to when the material forms a complex (instead of a manifold), and thus the angles are glued at the single vertex in the structure of an arbitrary planar graph (instead of a cycle). Like the earlier characterizations, we require all creases to fold mountain or valley, not remain unfolded flat; otherwise, the problem is known to be NP-complete (weakly for flat material and strongly for complexes). Equivalently, we efficiently characterize which combinatorially embedded planar graphs with prescribed edge lengths can fold flat, when all angles must be mountain or valley (not unfolded flat). Our algorithm runs in $O(n \log^3 n)$ time, improving on the previous best algorithm of $O(n^2 \log n)$.
