An official website of the United States government
A strip of square stamps can be folded in many ways such that all of the stamps are stacked in a single pile in the folded state. The stamp folding problem asks for the number of such foldings and has previously been studied extensively. We consider this problem with the additional restriction of fixing the mountain-valley assignment of each crease in the stamp pattern. We provide a closed form for counting the number of legal foldings on specific patterns of mountain-valley assignments, including a surprising appearance of the Catalan numbers. We describe results on upper and lower bounds for the number of ways to fold a given mountain-valley assignment on the strip of stamps, provide experimental evidence suggesting more general results, and include conjectures and open problems. Journal version
more »
« less
Face flips in origami tessellations
Given a locally flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on the plane) with a mountain-valley (MV) assignment $$\mu:E\to\{-1,1\}$$ indicating which creases in $$E$$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $$F$$ of $$G$$ to create a new MV assignment $$\mu_F$$ which equals $$\mu$$ except for all creases $$e$$ bordering $$F$$, where we have $$\mu_F(e)=-\mu(e)$$. In this paper we explore the configuration space of face flips that preserve local flat-foldability of the MV assignment for a variety of crease patterns $$G$$ that are tilings of the plane. We prove examples where $$\mu_F$$ results in a MV assignment that is either never, sometimes, or always locally flat-foldable, for various choices of $$F$$. We also consider the problem of finding, given two locally flat-foldable MV assignments $$\mu_1$$ and $$\mu_2$$ of a given crease pattern $$G$$, a minimal sequence of face flips to turn $$\mu_1$$ into $$\mu_2$$. We find polynomial-time algorithms for this in the cases where $$G$$ is either a square grid or the Miura-ori, and show that this problem is NP-complete in the case where $$G$$ is the triangle lattice.
more »
« less
- PAR ID:
- 10209600
- Date Published:
- Journal Name:
- Journal of computational geometry
- Volume:
- 11
- Issue:
- 1
- ISSN:
- 1920-180X
- Page Range / eLocation ID:
- 397–417
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)In this paper, we show that the rigid-foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from the partition problem, and that rigid-foldability with optional creases is NP-hard by a reduction from the 1-in-3 SAT problem. Unlike flat-foldabilty of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldabilltiy from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matters and reconfigurable robots.more » « less
-
Rigid origami, with applications ranging from nano-robots to unfolding solar sails in space, describes when a material is folded along straight crease line segments while keeping the regions between the creases planar. Prior work has found explicit equations for the folding angles of a flat-foldable degree-4 origami vertex and some cases of degree-6 vertices. We extend this work to generalized symmetries of the degree-6 vertex where all sector angles equal 60 ∘ . We enumerate the different viable rigid folding modes of these degree-6 crease patterns and then use second-order Taylor expansions and prior rigid folding techniques to find algebraic folding angle relationships between the creases. This allows us to explicitly compute the configuration space of these degree-6 vertices, and in the process we uncover new explanations for the effectiveness of Weierstrass substitutions in modelling rigid origami. These results expand the toolbox of rigid origami mechanisms that engineers and materials scientists may use in origami-inspired designs.more » « less
-
Evans, Robin; Shpitser, Ilya (Ed.)We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: \SCSKC and \DiffC. Given two submodular functions $$f$$ and $$g$$ where $$f$$ is monotone, the objective of \SCSKC problem is to find a set $$S$$ of size at most $$k$$ that maximizes $f(S)$ under the constraint that $$g(S)\leq \theta$$, for a given value of $$\theta$$. The problem of \DiffC focuses on finding a set $$S$$ of size at most $$k$$ such that $h(S) = f(S)-g(S)$$ is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of \SCSKC, we prove that the greedy algorithm produces a solution whose value is at least $$(1-1/e)f(\OPT) - A$, where $$A$$ is the data-dependent additive error. For the \DiffC problem, we design an algorithm that uses the \SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least $$(1-1/e)h(\OPT)-B$, where $$B$$ is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.more » « less
-
Abstract We study the fractional Yamabe problem first considered by Gonzalez-Qing [36] on the conformal infinity $$(M^{n}, \;[h])$$ of a Poincaré-Einstein manifold $$(X^{n+1}, \;g^{+})$$ with either $n=2$ or $$n\geq 3$$ and $$(M^{n}, \;[h])$$ locally flat, namely $(M, h),$ is locally conformally flat. However, as for the classical Yamabe problem, because of the involved quantization phenomena, the variational analysis of the fractional one exhibits a local situation and also a global one. The latter global situation includes the case of conformal infinities of Poincaré-Einstein manifolds of dimension either $n=2$ or of dimension $$n\geq 3$$ and which are locally flat, and hence the minimizing technique of Aubin [4] and Schoen [48] in that case clearly requires an analogue of the positive mass theorem of Schoen-Yau [49], which is not known to hold. Using the algebraic topological argument of Bahri-Coron [8], we bypass the latter positive mass issue and show that any conformal infinity of a Poincaré-Einstein manifold of dimension either $n=2$ or of dimension $$n\geq 3$$ and which is locally flat admits a Riemannian metric of constant fractional scalar curvature.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
