Folding equilateral plane graphs.
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 known to be impossible 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. Not only is the equilateral constraint necessary for this result, but we show that it is strongly NP-complete to decide whether a (nonequilateral) plane graph has a linear folded state. Equivalently, we show strong NP-completeness of deciding whether an abstract metric polyhedral complex with one central vertex has a noncrossing flat folded state with a specified "outside region". 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.