Who Needs Crossings?: Hardness of Plane Graph Rigidity
In Proceedings of the 32nd International Symposium on Computational Geometry, pages 3:1–3:15, June 2016.
In Journal of Computational Geometry, Special issue of selected papers from the 2016 Symposium on Computational Geometry, forthcoming, 2017.
On Folding and Unfolding with Linkages and Origami
Ph.D. Thesis, MIT, September 2016.
Prime Portraits
In Proceedings of the 19th Annual Bridges Conference, Jyväskylä, Finland, pages 359–362, August 2016.
Unfolding and Dissection of Multiple Cubes
In Proceedings of the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, pages 42–43, September 2016.
Flat Folding of Plane Graphs with Prescribed Angles and Edge Lengths
In Proceedings of the 22nd International Symposium on Graph Drawing, pages 272–283, September 2014.
Abstract:
Locked Rigid Origami with Multiple Degrees of Freedom
In Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education, page 80, August 2014.
Rigid Flattening of Polyhedra with Slits
In Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education, page 43, August 2014.
In Origami6: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education, pages 109–118, August 2014.
Continuously Flattening Polyhedra Using Straight Skeletons
In Proceedings of the 30th Annual Symposium on Computational Geometry, June 2014.
Abstract:
Finding a hamiltonian path in a cube with specified turns is hard.
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.
Algorithms for designing pop-up cards.
In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, pages 269–280, March 2013.
Computational complexity of piano-hinged dissections.
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A(6):1206–1212, 2014.
In Proceedings of the 29th European Workshop on Computational Geometry, pages 147–150, March 2013.
Abstract:
Folding equilateral plane graphs.
International Journal of Computational Geometry and Applications, 23(2):75–92, 2013.
In Proceedings of the 22nd International Symposium on Algorithms and Computation, December 2011.
See also the conference presentation of this paper.
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.
Hinged dissections exist.
Discrete & Computational Geometry, 47(1):150–186, 2012.
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.
A topologically convex vertex-ununfoldable polyhedron.
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.
Edge-unfolding orthogonal polyhedra is strongly NP-complete.
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.
Common developments of several different orthogonal boxes.
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.
Every large point set contains many collinear points or an empty pentagon.
Graphs and Combinatorics, 27(1):47–60, 2011.
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].
Shape replication through self-assembly and RNase enzymes.
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.
A categorical construction of ultrafilters.
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.
Configurations of rank-\(40r\) extremal even unimodular lattices (\(r=1,2,3\)).
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\).
Cauchy's arm lemma on a growing sphere.
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.
Pushing hypercubes around.
ArXiv:0802.3414, 2008.