Martin Demaine's Papers

Books

• Tribute to a Mathemagician
  (edited with Barry Cipra, Erik D. Demaine, and Tom Rodgers)
  A K Peters, November 2004.

Journal articles

• Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
  (joint work with Erik D. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine)
  Natural Computing, to appear. Special issue of selected papers from the 13th International Meeting on DNA Computing, 2007.

• Sand Drawings and Gaussian Graphs
  (joint work with Erik D. Demaine, Perouz Taslakian, and Godfried T. Toussaint)
  Journal of Mathematics and the Arts, volume 1, number 2, June 2007, pages 125–132.

• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
  (joint work with Erik D. Demaine)
  Graphs and Combinatorics, volume 23 (Supplement), June 2007, pages 195–208. Special issue on Computational Geometry and Graph Theory: The Akiyama-Chvatal Festschrift.

• Puzzles, Art, and Magic with Algorithms
  (joint work with Erik D. Demaine)
  Theory of Computing Systems, volume 39, number 3, June 2006, pages 473–481. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.

• Morpion Solitaire
  (joint work with Erik D. Demaine, Arthur Langerman, and Stefan Langerman)
  Theory of Computing Systems, volume 39, number 3, June 2006, pages 439–453. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.

• The Helium Stockpile: A Collaboration in Mathematical Folding Sculpture
  (joint work with Erik D. Demaine and A. Laurie Palmer)
  Leonardo, volume 39, number 3, June 2006, pages 233–235.

• Hinged Dissection of Polyominoes and Polyforms
  (joint work with Erik D. Demaine, David Eppstein, Greg N. Frederickson, and Erich Friedman)
  Computational Geometry: Theory and Applications, volume 31, number 3, June 2005, pages 237–262. Special issue of selected papers from the 11th Canadian Conference on Computational Geometry, 1999.

• Building Blocks and Excluded Sums
  (joint work with Erik D. Demaine, Alan Edelman, Charles E. Leiserson, and Per-Olof Persson)
  SIAM News, volume 38, number 1, January 2005, pages 1, 4, 6.

• When Can You Fold a Map?
  (joint work with Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena)
  Computational Geometry: Theory and Applications, volume 29, number 1, September 2004, pages 23–46. Special issue of selected papers from the 10th Annual Fall Workshop on Computational Geometry, 2000.

• Solitaire Clobber
  (joint work with Erik D. Demaine and Rudolf Fleischer)
  Theoretical Computer Science, volume 313, number 3, February 2004, pages 325–338. Special issue of selected papers presented at the Schloss Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, 2002.

• Pushing Blocks is Hard
  (joint work with Erik D. Demaine, Michael Hoffmann, and Joseph O'Rourke)
  Computational Geometry: Theory and Applications, volume 26, number 1, August 2003, pages 21–36. Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.

• Palindrome Recognition Using a Multidimensional Tape
  (joint work with Therese C. Biedl, Jonathan F. Buss, Erik D. Demaine, Mohammadtaghi Hajiaghayi, and Tomáš Vinař)
  Theoretical Computer Science, volume 302, number 1–3, June 2003, pages 475–480.

• Hinged Dissection of the Alphabet
  (joint work with Erik D. Demaine)
  Journal of Recreational Mathematics, volume 31, number 3, 2003, pages 204–207.

• Enumerating Foldings and Unfoldings between Polygons and Polytopes
  (joint work with Erik D. Demaine, Anna Lubiw, and Joseph O'Rourke)
  Graphs and Combinatorics, volume 18, number 1, 2002, pages 93–104.

• Balanced k-Colorings
  (joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
  Discrete Mathematics, volume 254, 2002, pages 19–32.

• A Note on Reconfiguring Tree Linkages: Trees can Lock
  (joint work with Therese Biedl, Erik Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides)
  Discrete Applied Mathematics, volume 117, number 1–3, 2002, pages 293–297.

• Locked and Unlocked Polygonal Chains in Three Dimensions
  (joint work with T. Biedl, E. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides)
  Discrete & Computational Geometry, volume 26, number 3, October 2001, pages 269–281.

• Polygons Cuttable by a Circular Saw
  (joint work with Erik D. Demaine and Craig S. Kaplan)
  Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 69–84. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.

• Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami
  (joint work with Erik D. Demaine and Joseph S. B. Mitchell)
  Computational Geometry: Theory and Applications, volume 16, number 1, 2000, pages 3–21. Special issue of selected papers from the 3rd CGC Workshop on Computational Geometry, 1998.

Book chapters

• The Complexity of Dyson Telescopes
  (joint work with Erik D. Demaine, Rudolf Fleischer, Robert A. Hearn, and Timo von Oertzen)
  in Games of No Chance III, to appear.

• Sliding-Coin Puzzles
  (joint work with Erik D. Demaine)
  in Tribute to a Mathemagician, 2004, pages 63–72, A K Peters.

• Fold-and-Cut Magic
  (joint work with Erik D. Demaine)
  in Tribute to a Mathemagician, 2004, pages 23–30, A K Peters.

• The Complexity of Clickomania
  (joint work with Therese C. Biedl, Erik D. Demaine, Rudolf Fleischer, Lars Jacobsen, and J. Ian Munro)
  in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 389–404, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

• Phutball Endgames are Hard
  (joint work with Erik D. Demaine and David Eppstein)
  in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 351–360, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

• Coin-Moving Puzzles
  (joint work with Erik D. Demaine and Helena A. Verrill)
  in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405–431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

Conference papers

• Computational Balloon Twisting: The Theory of Balloon Polyhedra
  (joint work with Erik D. Demaine and Vi Hart)
  in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), Montréal, Québec, Canada, August 13–15, 2008, to appear.

• Hinged Dissections Exist
  (joint work with Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, and Scott D. Kominers)
  in Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), College Park, Maryland, June 9–11, 2008, pages 110–119.

• Vertex Pops and Popturns
  (joint work with Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian, and Godfried Toussaint)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 137–140.

• On Rolling Cube Puzzles
  (joint work with Kevin Buchin, Maike Buchin, Erik D. Demaine, Dania El-Khechen, Sándor Fekete, Christian Knauer, André Schulz, and Perouz Taslakian)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 141–144.

• Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs
  (joint work with Nadia M. Benbernou, Erik D. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 13–16.

• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
  (joint work with Erik D. Demaine)
  in Abstracts from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007), Kyoto, Japan, June 11–15, 2007, to appear.

• Deflating The Pentagon
  (joint work with Erik D. Demaine, Diane L. Souvaine, and Perouz Taslakian)
  in Abstracts from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007), Kyoto, Japan, June 11–15, 2007, to appear.

• Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
  (joint work with Erik D. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine)
  in Proceedings of the 13th International Meeting on DNA Computing (DNA 2007), Lecture Notes in Computer Science, volume 4848, Memphis, Tennessee, June 4–8, 2007, to appear.

• Wrapping the Mozartkugel
  (joint work with Erik D. Demaine, John Iacono, and Stefan Langerman)
  in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 14–17.

• Deflating The Pentagon
  (joint work with Erik D. Demaine, Diane L. Souvaine, and Perouz Taslakian)
  in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 10–13.

• Curves in the Sand: Algorithmic Drawing
  (joint work with Mirela Damian, Erik D. Demaine, Vida Dujmović, Dania El-Khechen, Robin Flatland, John Iacono, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane L. Souvaine, Perouz Taslakian, and Godfried T. Toussaint)
  in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 11–14.

• Sand Drawings and Gaussian Graphs
  (joint work with Erik D. Demaine, Perouz Taslakian, and Godfried T. Toussaint)
  in Proceedings of the 9th Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES 2006), London, England, August 4–8, 2006, pages 79–88.

• Locked and Unlocked Chains of Planar Shapes
  (joint work with Robert Connelly, Erik D. Demaine, Sándor Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, and Günter Rote)
  in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 61–70.

• Hinged Dissection of Polypolyhedra
  (joint work with Erik D. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine)
  in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 205–217.

• Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane
  (joint work with Timothy Abbott, Erik D. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung)
  in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 61–64.

• Puzzles, Art, and Magic with Algorithms
  (joint work with Erik D. Demaine)
  in Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, volume 3341, Hong Kong, China, 2004, pages 1.

• Hinged Dissection of Polypolyhedra
  (joint work with Erik D. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine)
  in Abstracts from the 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, November 19–20, 2004, pages 16–17.

• Folding Paper Shopping Bags
  (joint work with Devin J. Balkcom and Erik D. Demaine)
  in Abstracts from the 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, November 19–20, 2004, pages 14–15.

• Morpion Solitaire
  (joint work with Erik D. Demaine, Arthur Langerman, and Stefan Langerman)
  in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 53–64.

• Puzzles, Art, and Magic with Algorithms
  (joint work with Erik D. Demaine)
  in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 7–15.

• Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles
  (joint work with Therese Biedl, Timothy M. Chan, Erik D. Demaine, Paul Nijjar, Ryuhei Uehara, and Ming-wei Wang)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 105–108.

• Solitaire Clobber
  (joint work with Erik D. Demaine and Rudolf Fleischer)
  in Proceedings of the 3rd International Conference on Computers and Games (CG 2002), Lecture Notes in Computer Science, volume 2883, Edmonton, Alberta, Canada, July 25–27, 2002, pages 188–200.

• The CCCG 2001 Logo
  (joint work with Erik D. Demaine and Anna Lubiw)
  in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, iv–v.

• When Can You Fold a Map?
  (joint work with Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena)
  in Proceedings of the 7th Workshop on Algorithms and Data Structures (WADS 2001), Lecture Notes in Computer Science, volume 2125, Providence, Rhode Island, August 8–10, 2001, pages 401–413.

• Recent Results in Computational Origami
  (joint work with Erik D. Demaine)
  in Origami$^3$: Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001), Monterey, California, March 9–11, 2001, pages 3–16, A K Peters.

• Enumerating Foldings and Unfoldings between Polygons and Polytopes
  (joint work with Erik D. Demaine, Anna Lubiw, and Joseph O'Rourke)
  in Abstracts from the Japan Conference on Discrete and Computational Geometry (JCDCG 2000), Tokyo, Japan, November 22–25, 2000, pages 9–12.

• When Can You Fold a Map?
  (joint work with Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena)
  in Abstracts from the 10th Annual Fall Workshop on Computational Geometry, Stony Brook, New York, October 27–28, 2000.

• Balanced k-Colorings
  (joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
  in Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000), Lecture Notes in Computer Science, volume 1893, Bratislava, Slovak Republic, August 28–September 1, 2000, pages 202–211.

• Polygons Cuttable by a Circular Saw
  (joint work with Erik D. Demaine and Craig S. Kaplan)
  in Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), Fredericton, New Brunswick, Canada, August 16–18, 2000, pages 1–6.

• PushPush and Push-1 are NP-hard in 2D
  (joint work with Erik D. Demaine and Joseph O'Rourke)
  in Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), Fredericton, New Brunswick, Canada, August 16–18, 2000, pages 211–219.

• Hinged Dissection of Polyominoes and Polyiamonds
  (joint work with Erik D. Demaine, David Eppstein, and Erich Friedman)
  in Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15–18, 1999.

• Polyhedral Sculptures with Hyperbolic Paraboloids
  (joint work with Erik D. Demaine and Anna Lubiw)
  in Proceedings of the 2nd Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES'99), Winfield, Kansas, July 30–August 1, 1999, pages 91–100.

• Metamorphosis of the Cube
  (joint work with Erik Demaine, Anna Lubiw, Joseph O'Rourke, and Irena Pashchenko)
  in 8th Annual Video Review of Computational Geometry, Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SoCG'99), Miami Beach, Florida, June 13–16, 1999, pages 409–410.

• Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami
  (joint work with Erik D. Demaine and Joseph S. B. Mitchell)
  in Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SoCG'99), Miami Beach, Florida, June 13–16, 1999, pages 105–114.

• Folding and One Straight Cut Suffice
  (joint work with Erik D. Demaine and Anna Lubiw)
  in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, January 17–19, 1999, pages 891–892.

• Locked and Unlocked Polygonal Chains in 3D
  (joint work with T. Biedl, E. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides)
  in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, January 17–19, 1999, pages 866–867.

• Folding and Cutting Paper
  (joint work with Erik D. Demaine and Anna Lubiw)
  in Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98), Lecture Notes in Computer Science, volume 1763, Tokyo, Japan, December 9–12, 1998, pages 104–117.

• Folding Any Silhouette from a Strip
  (joint work with Erik D. Demaine and Joseph S. B. Mitchell)
  in Abstracts from the 3rd CGC Workshop on Computational Geometry (CGC'98), Providence, Rhode Island, October 11–12, 1998.

• Planar Drawings of Origami Polyhedra
  (joint work with Erik D. Demaine)
  in Proceedings of the 6th Symposium on Graph Drawing (GD'98), Lecture Notes in Computer Science, volume 1547, Montréal, Québec, Canada, August 13–15, 1998, pages 438–440.

• Hiding Disks in Folded Polygons
  (joint work with Therese C. Biedl, Erik D. Demaine, Anna Lubiw, and Godfried T. Toussaint)
  in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.

• Unfolding Some Classes of Orthogonal Polyhedra
  (joint work with Therese Biedl, Erik Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, Steve Robbins, and Sue Whitesides)
  in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.

• On Reconfiguring Tree Linkages: Trees can Lock
  (joint work with Therese Biedl, Erik Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides)
  in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.

Technical reports

• Solitaire Clobber
  (joint work with Erik D. Demaine and Rudolf Fleischer)
  Technical Report HKUST-TCSC-2002-05, Hong Kong University of Science and Technology, April 2002.

• On Reconfiguring Tree Linkages: Trees can Lock
  (joint work with Therese Biedl, Erik Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides)
  Technical Report SOCS-00.7, School of Computer Science, McGill University, September 2000.

• Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes
  (joint work with Erik Demaine, Anna Lubiw, and Joseph O'Rourke)
  Technical Report 069, Smith College, July 2000.

• Balanced k-Colorings
  (joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
  Technical Report CS-2000-08, Department of Computer Science, University of Waterloo, March 2000.

• PushPush is NP-hard in 2D
  (joint work with Erik D. Demaine and Joseph O'Rourke)
  Technical Report 065, Smith College, January 2000.

• Locked and Unlocked Polygonal Chains in 3D
  (joint work with T. Biedl, E. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides)
  Technical Report 060, Smith College, October 1999.

• Planar Drawings of Origami Polyhedra
  (joint work with Erik D. Demaine)
  Technical Report CS-98-17, Department of Computer Science, University of Waterloo, August 1998.

• Computing Extreme Origami Bases
  (joint work with Erik D. Demaine)
  Technical Report CS-97-22, Department of Computer Science, University of Waterloo, May 1997.

Manuscripts

• Coin-Flipping Magic
  (joint work with Nadia Benbernou, Erik D. Demaine, and Benjamin Rossman)
  Manuscript, April 2008. Presented at \emph{Gathering for Gardner 8