Martin L. Demaine

CoRR, 2023

Developing a tetramonohedron with minimum cut length.

[BibT_eX]

[DOI]

Comput. Geom., 2023

2022

Orthogonal Fold & Cut.

[BibT_eX]

[DOI]

CoRR, 2022

Rolling Polyhedra on Tessellations.

[BibT_eX]

[DOI]

Proceedings of the 11th International Conference on Fun with Algorithms, 2022

2021

On the effects of hierarchical self-assembly for reducing program-size complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Folding polyominoes with holes into a cube.

[BibT_eX]

[DOI]

Comput. Geom., 2021

Continuous flattening of all polyhedral manifolds using countably infinite creases.

[BibT_eX]

[DOI]

Comput. Geom., 2021

Snipperclips: Cutting tools into desired polygons using themselves.

[BibT_eX]

[DOI]

Comput. Geom., 2021

Tatamibari Is NP-Complete.

[BibT_eX]

[DOI]

Proceedings of the 10th International Conference on Fun with Algorithms, 2021

Any Regular Polyhedron Can Transform to Another by O(1) Refoldings.

[BibT_eX]

Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

2020

Rectangular Unfoldings of Polycubes.

[BibT_eX]

[DOI]

J. Inf. Process., 2020

Flat Folding a Strip with Parallel or Nonacute Zigzag Creases with Mountain-Valley Assignment.

[BibT_eX]

[DOI]

J. Inf. Process., 2020

Adventures in Maze Folding Art.

[BibT_eX]

[DOI]

Ivan Tadeu Ferreira Antunes Filho

J. Inf. Process., 2020

Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players.

[BibT_eX]

[DOI]

J. Inf. Process., 2020

Tetris is NP-hard even with O(1) Rows or Columns.

[BibT_eX]

[DOI]

J. Inf. Process., 2020

Path Puzzles: Discrete Tomography with a Path Constraint is Hard.

[BibT_eX]

[DOI]

Graphs Comb., 2020

Tetris is NP-hard even with $O(1)$ rows or columns.

[BibT_eX]

[DOI]

CoRR, 2020

Escaping a Polygon.

[BibT_eX]

[DOI]

CoRR, 2020

Universal hinge patterns for folding strips efficiently into any grid polyhedron.

[BibT_eX]

[DOI]

Comput. Geom., 2020

Existence and Hardness of Conveyor Belts.

[BibT_eX]

[DOI]

Joshua P. Swanson

Electron. J. Comb., 2020

Some Polycubes Have No Edge Zipper Unfolding.

[BibT_eX]

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra.

[BibT_eX]

David Eppstein

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

Folding Small Polyominoes into a Unit Cube.

[BibT_eX]

Kingston Yao Czajkowski

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2019

Some Polycubes Have No Edge-Unzipping.

[BibT_eX]

[DOI]

CoRR, 2019

Rectangular Unfoldings of Polycubes.

[BibT_eX]

Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

2018

An End-to-End Approach to Self-Folding Origami Structures.

[BibT_eX]

[DOI]

Byoungkwon An

Shuhei Miyashita

Aaron C. Ong

Michael Thomas Tolley

IEEE Trans. Robotics, 2018

Flat foldings of plane graphs with prescribed angles and edge lengths.

[BibT_eX]

[DOI]

J. Comput. Geom., 2018

Folding Polyominoes into (Poly)Cubes.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2018

Conic Crease Patterns with Reflecting Rule Lines.

[BibT_eX]

[DOI]

CoRR, 2018

Losing at Checkers is Hard.

[BibT_eX]

[DOI]

CoRR, 2018

Pachinko.

[BibT_eX]

[DOI]

Comput. Geom., 2018

Bumpy pyramid folding.

[BibT_eX]

[DOI]

Comput. Geom., 2018

Packing Cube Nets into Rectangles with O(1) Holes.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry, Graphs, and Games, 2018

Toward Unfolding Doubly Covered n-Stars.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry, Graphs, and Games, 2018

Negative Instance for the Edge Patrolling Beacon Problem.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry, Graphs, and Games, 2018

2017

Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, ...

[BibT_eX]

[DOI]

J. Inf. Process., 2017

Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard.

[BibT_eX]

[DOI]

J. Inf. Process., 2017

Folding and Punching Paper.

[BibT_eX]

[DOI]

J. Inf. Process., 2017

Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares.

[BibT_eX]

[DOI]

J. Inf. Process., 2017

Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard.

[BibT_eX]

[DOI]

CoRR, 2017

Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Computing 3SAT on a Fold-and-Cut Machine.

[BibT_eX]

Proceedings of the 29th Canadian Conference on Computational Geometry, 2017

2016

Who Needs Crossings? Hardness of Plane Graph Rigidity.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Linear-time algorithm for sliding tokens on trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Fun with fonts: Algorithmic typography.

[BibT_eX]

[DOI]

Fernando Sánchez Villaamil

Theor. Comput. Sci., 2015

Zig-Zag Numberlink is NP-Complete.

[BibT_eX]

[DOI]

Blair D. Sullivan

J. Inf. Process., 2015

Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations.

[BibT_eX]

[DOI]

CoRR, 2015

Continuous Flattening of Orthogonal Polyhedra.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Dissection with the Fewest Pieces is Hard, Even to Approximate.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

A Dissimilarity Measure for Comparing Origami Crease Patterns.

[BibT_eX]

Seung Man Oh

Proceedings of the ICPRAM 2015, 2015

2014

UNO is hard, even for a single player.

[BibT_eX]

[DOI]

Nicholas J. A. Harvey

Takeaki Uno

Yushi Uno

Theor. Comput. Sci., 2014

Picture-Hanging Puzzles.

[BibT_eX]

[DOI]

Yair N. Minsky

Ronald L. Rivest

Mihai Patrascu

Theory Comput. Syst., 2014

Covering Folded Shapes.

[BibT_eX]

[DOI]

J. Comput. Geom., 2014

Computational Complexity of Piano-Hinged Dissections.

[BibT_eX]

[DOI]

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2014

Reprint of: Refold rigidity of convex polyhedra.

[BibT_eX]

[DOI]

Comput. Geom., 2014

Polynomial-Time Algorithm for Sliding Tokens on Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

An end-to-end approach to making self-folded 3D surface shapes by uniform heating.

[BibT_eX]

[DOI]

Byoungkwon An

Shuhei Miyashita

Michael Thomas Tolley

Proceedings of the 2014 IEEE International Conference on Robotics and Automation, 2014

One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Continuously Flattening Polyhedra Using Straight Skeletons.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

Finding a Hamiltonian Path in a Cube with Specified Turns is Hard.

[BibT_eX]

[DOI]

J. Inf. Process., 2013

Folding Equilateral Plane graphs.

[BibT_eX]

[DOI]

Isaac Shapiro-Ellowitz

Int. J. Comput. Geom. Appl., 2013

Refold rigidity of convex polyhedra.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Bounded-degree polyhedronization of point sets.

[BibT_eX]

[DOI]

Andrew Winslow

Comput. Geom., 2013

Non-crossing matchings of points with geometric objects.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Algorithms for Designing Pop-Up Cards.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Zipper Unfoldability of Domes and Prismoids.

[BibT_eX]

[DOI]

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Variations on Instant Insanity.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

NP-completeness of generalized Kaboozle.

[BibT_eX]

[DOI]

J. Inf. Process., 2012

Ghost chimneys.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2012

Hinged Dissections Exist.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2012

One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece

[BibT_eX]

[DOI]

CoRR, 2012

Two Hands Are Better Than One (up to constant factors)

[BibT_eX]

[DOI]

CoRR, 2012

Any Monotone Function Is Realized by Interlocked Polygons.

[BibT_eX]

[DOI]

Algorithms, 2012

2011

(Non)Existence of Pleated Folds: How Paper Folds Between Creases.

[BibT_eX]

[DOI]

Graphs Comb., 2011

Continuous Blooming of Convex Polyhedra.

[BibT_eX]

[DOI]

Graphs Comb., 2011

Algorithmic Folding Complexity.

[BibT_eX]

[DOI]

Graphs Comb., 2011

Covering points by disjoint boxes with outliers.

[BibT_eX]

[DOI]

Comput. Geom., 2011

Meshes Preserving Minimum Feature Size.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry - XIV Spanish Meeting on Computational Geometry, 2011

Algorithms for Solving Rubik's Cubes.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

Edge-guarding Orthogonal Polyhedra.

[BibT_eX]

[DOI]

Jorge Urrutia

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Convexifying Polygons Without Losing Visibilities.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Common Developments of Several Different Orthogonal Boxes.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

A Topologically Convex Vertex-Ununfoldable Polyhedron.

[BibT_eX]

[DOI]

Zachary Abel

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Locked and Unlocked Chains of Planar Shapes.

[BibT_eX]

[DOI]

Ares Ribó

Günter Rote

Discret. Comput. Geom., 2010

The complexity of UNO

[BibT_eX]

[DOI]

CoRR, 2010

Shape Replication through Self-Assembly and RNase Enzymes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Matching Points with Things.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

UNO Is Hard, Even for a Single Player.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Kaboozle Is NP-complete, Even in a Strip.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Making Polygons by Simple Folds and One Straight Cut.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry, Graphs and Applications, 2010

Common Unfoldings of Polyominoes and Polycubes.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry, Graphs and Applications, 2010

Zipper unfoldings of polyhedral complexes.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

Any monotone boolean function can be realized by interlocked polygons.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009

A Universal Crease Pattern for Folding Orthogonal Shapes

[BibT_eX]

[DOI]

CoRR, 2009

Minimum feature size preserving decompositions

[BibT_eX]

[DOI]

CoRR, 2009

Wrapping spheres with flat paper.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Dynamic ham-sandwich cuts in the plane.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Minimal Locked Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Folding a Better Checkerboard.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Algorithmic Folding Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Staged self-assembly: nanomanufacture of arbitrary shapes with O (1) glues.

[BibT_eX]

[DOI]

Nat. Comput., 2008

Cauchy's Arm Lemma on a Growing Sphere

[BibT_eX]

[DOI]

CoRR, 2008

Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues

[BibT_eX]

[DOI]

CoRR, 2008

A Locked Orthogonal Tree

[BibT_eX]

[DOI]

CoRR, 2008

Computational Balloon Twisting: The Theory of Balloon Polyhedra.

[BibT_eX]

Vi Hart

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007

Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity.

[BibT_eX]

[DOI]

Graphs Comb., 2007

Deflating the Pentagon.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry and Graph Theory, 2007

On Rolling Cube Puzzles.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

Disjoint Segments Have Convex Partitions with 2-Edge Connected Dual Graphs.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

Vertex Pops and Popturns.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006

Morpion Solitaire.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

Puzzles, Art, and Magic with Algorithms.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

Curves in the Sand: Algorithmic Drawing.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Hinged dissection of polyominoes and polyforms.

[BibT_eX]

[DOI]

Comput. Geom., 2005

Hinged Dissection of Polypolyhedra.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane.

[BibT_eX]

[DOI]

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004

Solitaire Clobber.

[BibT_eX]

[DOI]

Rudolf Fleischer

Theor. Comput. Sci., 2004

When can you fold a map?

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Saurabh Sethia

Steven Skiena

Comput. Geom., 2004

2003

Palindrome recognition using a multidimensional tape.

[BibT_eX]

[DOI]

Tomás Vinar

Theor. Comput. Sci., 2003

Pushing blocks is hard.

[BibT_eX]

[DOI]

Comput. Geom., 2003

2002

Enumerating Foldings and Unfoldings Between Polygons and Polytopes.

[BibT_eX]

[DOI]

Graphs Comb., 2002

Balanced k-colorings.

[BibT_eX]

[DOI]

Discret. Math., 2002

A note on reconfiguring tree linkages: trees can lock.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2002

Coin-Moving Puzzles

[BibT_eX]

[DOI]

Helena A. Verrill

CoRR, 2002

Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles.

[BibT_eX]

[DOI]

Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

2001

Locked and Unlocked Polygonal Chains in Three Dimensions.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2001

The Complexity of Clickomania

[BibT_eX]

[DOI]

CoRR, 2001

Polygons cuttable by a circular saw.

[BibT_eX]

[DOI]

Craig S. Kaplan

Comput. Geom., 2001

The cccg 2001 logo.

[BibT_eX]

[DOI]

Anna Lubiw

Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

2000

Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes

[BibT_eX]

[DOI]

CoRR, 2000

PushPush is NP-hard in 2D

[BibT_eX]

[DOI]

Joseph O'Rourke

CoRR, 2000

Phutball Endgames are Hard

[BibT_eX]

[DOI]

David Eppstein

CoRR, 2000

Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami.

[BibT_eX]

[DOI]

Comput. Geom., 2000

PushPush and Push-1 are NP-hard in 2D.

[BibT_eX]

[DOI]

Joseph O'Rourke

Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999

Folding and One Straight Cut Suffice.

[BibT_eX]

[DOI]

Anna Lubiw

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Locked and Unlocked Polygonal Chains in 3D.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Metamorphosis of the Cube.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Hinged dissections of polyominoes and polyforms.

[BibT_eX]

[DOI]

Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1998

Folding and Cutting Paper.

[BibT_eX]

[DOI]

Anna Lubiw

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998

Planar Drawings of Origami Polyhedra.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 6th International Symposium, 1998

Hiding disks in folded polygons.

[BibT_eX]

[DOI]

Proceedings of the 10th Canadian Conference on Computational Geometry, 1998

Unfolding some classes of orthogonal polyhedra.

[BibT_eX]

[DOI]

Proceedings of the 10th Canadian Conference on Computational Geometry, 1998

On reconfiguring tree linkages: Trees can lock.

[BibT_eX]

[DOI]