# Research and Publications

1. Who Needs Crossings?: Hardness of Plane Graph Rigidity

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl.

1. In Proceedings of the 32nd International Symposium on Computational Geometry, pages 3:1–3:15, June 2016.

2. In Journal of Computational Geometry, Special issue of selected papers from the 2016 Symposium on Computational Geometry, forthcoming, 2017.

2. On Folding and Unfolding with Linkages and Origami

Ph.D. Thesis, MIT, September 2016.

3. Prime Portraits

In Proceedings of the 19th Annual Bridges Conference, Jyväskylä, Finland, pages 359–362, August 2016.

4. Unfolding and Dissection of Multiple Cubes

Zachary Abel, Brad Ballinger, Erik D. Demaine, Martin L. Demaine, Jeff Erikson, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jayson Lynch, and Ryuhei Uehara. In Proceedings of the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, pages 42–43, September 2016.

5. Flat Folding of Plane Graphs with Prescribed Angles and Edge Lengths

Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara. In Proceedings of the 22nd International Symposium on Graph Drawing, pages 272–283, September 2014.

Abstract:

When can a plane graph with prescribed edge lengths and prescribed angles (from among {0, 180°, 360°}) be folded flat to lie in an infinitesimally thick line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each vertex should sum to 360°, and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states.
6. Locked Rigid Origami with Multiple Degrees of Freedom

Zachary Abel, Thomas Hull, and Tomohiro Tachi. In Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education, page 80, August 2014.

7. Rigid Flattening of Polyhedra with Slits

Zachary Abel, Robert Connelly, Erik D. Demaine, Martin L. Demaine, Thomas Hull, Anna Lubiw, and Tomohiro Tachi.

1. In Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education, page 43, August 2014.

2. In Origami6: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education, pages 109–118, August 2014.

8. Continuously Flattening Polyhedra Using Straight Skeletons

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jin-Ichi Itoh, Anna Lubiw, Chie Nara, and Joseph O'Rourke. In Proceedings of the 30th Annual Symposium on Computational Geometry, June 2014.

Abstract:

We prove that a surprisingly simple algorithm folds the surface of every convex polyhedron, in any dimension, into a flat folding by a continuous motion, while preserving intrinsic distances and avoiding crossings. The flattening respects the straight-skeleton gluing, meaning that points of the polyhedron touched by a common ball inside the polyhedron come into contact in the flat folding, which answers an open question in the book Geometric Folding Algorithms. The primary creases in our folding process can be found in quadratic time, though necessarily, creases must roll continuously, and we show that the full crease pattern can be exponential in size. We show that our method solves the fold-and-cut problem for convex polyhedra in any dimension. As an additional application, we show how a limiting form of our algorithm gives a general design technique for flat origami tessellations, for any spiderweb (planar graph with all-positive equilibrium stress).
9. Finding a hamiltonian path in a cube with specified turns is hard.

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. Journal of Information Processing, Special issue on "Mathematics of Puzzles", 21(3):368–377, 2013.

Abstract:

We prove the NP-completeness of finding a Hamiltonian path in an $$N \times N \times N$$ cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of $$N^3$$ unit cubes, joined at face centers (usually by a cord passing through all the cubes), into an $$N \times N \times N$$ cube. Along the way, we prove a universality result that zig-zag chains (which must turn every unit) can fold into any polycube after $$4 \times 4 \times 4$$ refinement, or into any Hamiltonian polycube after $$2 \times 2 \times 2$$ refinement.

10. Algorithms for designing pop-up cards.

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane Souvaine, Giovanni Viglietta, and Andrew Winslow. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, pages 269–280, March 2013.

11. Computational complexity of piano-hinged dissections.

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, and Ryuhei Uehara.

1. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A(6):1206–1212, 2014.

2. In Proceedings of the 29th European Workshop on Computational Geometry, pages 147–150, March 2013.

Abstract:

We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
12. Folding equilateral plane graphs.

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, and Isaac Shapiro-Ellowitz.

1. International Journal of Computational Geometry and Applications, 23(2):75–92, 2013.

2. In Proceedings of the 22nd International Symposium on Algorithms and Computation, December 2011.

Abstract:

We consider two types of folding applied to equilateral plane graph linkages. First, under continuous folding motions, we show how to reconfigure any linear equilateral tree (lying on a line) into a canonical configuration. By contrast, such reconfiguration is not always possible for linear (nonequilateral) trees and for (nonlinear) equilateral trees. Second, under instantaneous folding motions, we show that an equilateral plane graph has a noncrossing linear folded state if and only if it is bipartite. Furthermore, we show that the equilateral constraint is necessary for this result, by proving that it is strongly NP-complete to decide whether a (nonequilateral) plane graph has a linear folded state. Equivalently, we show the strong NP-completeness of deciding whether an abstract metric polyhedral complex with one central vertex has a noncrossing flat folded state. By contrast, the analogous problem for a polyhedral manifold with one central vertex (single-vertex origami) is only weakly NP-complete.

13. Hinged dissections exist.

Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, and Scott D. Kominers.

1. Discrete & Computational Geometry, 47(1):150–186, 2012.

2. In Proceedings of the 24th Annual Symposium on Computational Geometry, pages 110–119, June 2008. See also the conference presentation of this paper.

Abstract:

We prove that any finite collection of polygons of equal area has a common hinged-dissection. That is, for any such collection of polygons there exists a chain of polygons hinged at vertices that can be folded in the plane continuously without self-intersection to form any polygon in the collection. This result settles the open problem about the existence of hinged dissections between pairs of polygons that goes back implicitly to 1864 and has been studied extensively in the past ten years. Our result generalizes and indeed builds upon the result from 1814 that polygons have common dissections (without hinges). Our proofs are constructive, giving explicit algorithms in all cases. For two planar polygons whose vertices lie on a rational grid, both the number of pieces and the running time required by our construction are pseudopolynomial. This bound is the best possible, even for unhinged dissections. Hinged dissections have possible applications to reconfigurable robotics, programmable matter, and nanomanufacturing.

14. A topologically convex vertex-ununfoldable polyhedron.

Zachary Abel, Erik D. Demaine, and Martin L. Demaine. In Proceedings of the 23st Canadian Conference on Computational Geometry, pages 89–91, August 2011. See also the conference presentation of this paper.

Abstract:

We construct a polyhedron that is topologically convex (i.e., has the graph of a convex polyhedron) yet has no vertex unfolding: no matter how we cut along the edges and keep faces attached at vertices to form a connected (hinged) surface, the surface necessarily unfolds with overlap.

15. Edge-unfolding orthogonal polyhedra is strongly NP-complete.

Zachary Abel and Erik D. Demaine. In Proceedings of the 23st Canadian Conference on Computational Geometry, pages 83–88, August 2011. See also the conference presentation of this paper.

Abstract:

We prove that it is strongly NP-complete to decide whether a given orthogonal polyhedron has a (nonoverlapping) edge-unfolding. The result holds even when the polyhedron is topologically convex, i.e., is homeomorphic to a sphere, has faces that are homeomorphic to disks, and where every two faces share at most one edge.

16. Common developments of several different orthogonal boxes.

Zachary Abel, Erik Demaine, Martin Demaine, Hiroaki Matsui, Günter Rote, and Ryuhei Uehara. In Proceedings of the 23st Canadian Conference on Computational Geometry, pages 77–82, August 2011.

Abstract:

We investigate the problem of finding common developments that fold to plural incongruent orthogonal boxes. It was shown that there are infinitely many orthogonal polygons that fold to two incongruent orthogonal boxes in 2008. In this paper, we first show that there is an orthogonal polygon that folds to three boxes of size $$1 \times 1 \times 5$$, $$1 \times 2 \times 3$$, and $$0 \times 1 \times 11$$. Although we have to allow a box to have volume 0, this solves the open problem mentioned in literature. Moreover, once we admit that a box can be of volume 0, a long rectangular strip can be folded to an arbitrary number of boxes of volume 0. We next consider finding common non-orthogonal developments that fold to plural incongruent orthogonal boxes. In literature, only orthogonal folding lines or with 45 degree lines were considered. In this paper, we show some polygons that can fold to two incongruent orthogonal boxes in more general directions.

17. Every large point set contains many collinear points or an empty pentagon.

Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Por, and David R. Wood.

1. Graphs and Combinatorics, 27(1):47–60, 2011.

2. In Proceedings of the 21st Canadian Conference on Computational Geometry, August 2009.

Abstract:

We prove the following generalised empty pentagon theorem for every integer $$\ell \ge 2$$, every sufficiently large set of points in the plane contains $$\ell$$ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of Kára, Pór, and Wood [Discrete Comput. Geom. 34(3):497–506, 2005].

18. Shape replication through self-assembly and RNase enzymes.

Zachary Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Robin Flatland, Scott D. Kominers, Robert Schweller, and Martin L. Demaine. In Proceedings of the 2010 ACM-SIAM Symposium on Discrete Algorithms, pages 1045–1064, January 2010.

Abstract:

We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only $$O(1)$$ distinct tile types and $$O(1)$$ stages. Further, we show how to replicate precisely $$n$$ copies of a shape using $$O(\log n)$$ stages and $$O(1)$$ tile types.

19. A categorical construction of ultrafilters.

Daniel Litt, Zachary Abel, and Scott Duke Kominers. Rocky Mountain Journal of Mathematics, 40(5):1611–1617, 2010.

Abstract:

Ultrafilters are useful mathematical objects having applications in nonstandard analysis, Ramsey theory, Boolean algebra, topology and other areas of mathematics. In this note, we provide a categorical construction of ultrafilters in terms of the inverse limit of an inverse family of finite partitions; this is an elementary and intuitive presentation of a consequence of the profiniteness of Stone spaces. We then apply this construction to answer a question of Rosinger in the negative.

20. Configurations of rank-$$40r$$ extremal even unimodular lattices ($$r=1,2,3$$).

Scott Duke Kominers and Zachary Abel. Journal de Théorie des Nombres de Bordeaux, 20(2):365–371, 2008.

Abstract:

We show that if $$L$$ is an extremal even unimodular lattice of rank $$40r$$ with $$r=1,2,3$$, then $$L$$ is generated by its vectors of norms $$4r$$ and $$4r+2$$. Our result is an extension of Ozeki's result for the case $$r=1$$.

21. Cauchy's arm lemma on a growing sphere.

Zachary Abel, David Charlton, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, and Godfried Toussaint. ArXiv:0804.0986, April 2008.

Abstract:

We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases. The main focus of this work is a comparison of three alternate proofs, to show the links between Toponogov's Comparison Theorem, Legendre's Theorem and Cauchy's Arm Lemma.

22. Pushing hypercubes around.

Zachary Abel and Scott D. Kominers. ArXiv:0802.3414, 2008.