In this paper, we extend multiple results previously known for map folds on rectangular grids, to maps on an equilateral triangle grid. Specifically, we show that it is always possible to fold a 1D equilateral triangle strip in the general folding model, while it is (strongly) NP-complete to determine whether various subsets of an equilateral triangle grid can be folded via various simple folds; in particular for the assigned polyiamond paper in all models, and for assigned convex paper and unassigned polyiamond paper in the some- and all-layers models.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Equilateral Triangle Map Folding

  • G. W. van der Heijden,
  • I. Kostitsyna,
  • J. S. Ku

摘要

In this paper, we extend multiple results previously known for map folds on rectangular grids, to maps on an equilateral triangle grid. Specifically, we show that it is always possible to fold a 1D equilateral triangle strip in the general folding model, while it is (strongly) NP-complete to determine whether various subsets of an equilateral triangle grid can be folded via various simple folds; in particular for the assigned polyiamond paper in all models, and for assigned convex paper and unassigned polyiamond paper in the some- and all-layers models.