Erik Demaine

Q: What Schools Are Affiliated With Erik Demaine

Erik Demaine is affiliated with the following schools: University of Waterloo, Dalhousie University, Massachusetts Institute of Technology

Erik Demaine's AcademicInfluence.com Rankings

Erik Demaine

Computer Science

#535

World Rank

#555

Historical Rank

Database

#1001

World Rank

#1054

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Erik Demaine Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Erik D. Demaine is a Canadian-American professor of computer science at the Massachusetts Institute of Technology and a former child prodigy. Early life and education Demaine was born in Halifax, Nova Scotia, to mathematician and sculptor Martin L. Demaine and Judy Anderson. From the age of 7, he was identified as a child prodigy and spent time traveling across North America with his father. He was home-schooled during that time span until entering university at the age of 12.

(See a Problem?)

Erik Demaine's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

A method for building self-folding machines (2014) (753)
Anchor-Free Distributed Localization in Sensor Networks (2003) (546)
Programmable matter by folding (2010) (526)
Geometric folding algorithms - linkages, origami, polyhedra (2007) (519)
Frequency Estimation of Internet Packet Streams with Limited Space (2002) (516)
Mobile-assisted localization in wireless sensor networks (2005) (317)
Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs (2005) (309)
Cache-oblivious B-trees (2000) (307)
Correlation clustering in general weighted graphs (2006) (305)
PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation (2002) (278)
An optimal decomposition algorithm for tree edit distance (2006) (273)
Representing Trees of Higher Degree (2005) (254)
Self-folding with shape memory composites† (2013) (246)
On the complexity of reconfiguration problems (2008) (228)
Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity (2007) (223)
Deploying sensor networks with guaranteed capacity and fault tolerance (2005) (222)
The Bidimensionality Theory and Its Algorithmic Applications (2008) (222)
Generalized communicators in the Message Passing Interface (1996) (221)
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory (2001) (214)
Algorithmic graph minor theory: Decomposition, approximation, and coloring (2005) (208)
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2003) (207)
Games, puzzles and computation (2009) (203)
Tetris is hard, even to approximate (2002) (201)
Logarithmic Lower Bounds in the Cell-Probe Model (2005) (195)
Adaptive set intersections, unions, and differences (2000) (183)
Geometric Folding Algorithms: Linkages (2007) (181)
Bidimensionality: new connections between FPT algorithms and PTASs (2005) (175)
Straightening polygonal arcs and convexifying polygonal cycles (2000) (174)
Identifying frequent items in sliding windows over on-line packet streams (2003) (161)
Energy-Efficient Algorithms (2016) (159)
Two Simplified Algorithms for Maintaining Order in a List (2002) (157)
Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs (2005) (157)
EpiChord: parallelizing the chord lookup algorithm with reactive routing state management (2004) (153)
Combination can be hard: approximability of the unique coverage problem (2006) (151)
Minimizing movement (2007) (146)
K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data (2002) (137)
Linearity of grid minors in treewidth with applications through bidimensionality (2008) (136)
Subquadratic Algorithms for 3SUM (2005) (131)
Correlation Clustering with Partial Information (2003) (130)
Cache-oblivious priority queue and graph algorithm applications (2002) (124)
Folding flat silhouettes and wrapping polyhedral packages: new results in computational origami (1999) (120)
Optimal covering tours with turn costs (2001) (119)
Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs (2004) (115)
Deploying Sensor Networks With Guaranteed Fault Tolerance (2010) (111)
Poster abstract: anchor-free distributed localization in sensor networks (2003) (109)
The price of anarchy in network creation games (2007) (107)
Dynamic Optimality - Almost (2004) (103)
Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues (2008) (102)
Online Routing in Convex Subdivisions (2000) (101)
Online searching with turn cost (2004) (97)
Minimizing the Diameter of a Network Using Shortcut Edges (2010) (93)
Approximation algorithms via contraction decomposition (2007) (91)
On Cartesian Trees and Range Minimum Queries (2009) (90)
Bidimensional Parameters and Local Treewidth (2004) (90)
Programmable Assembly With Universally Foldable Strings (Moteins) (2011) (84)
Equivalence of local treewidth and linear local treewidth and its algorithmic applications (2004) (84)
Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM (2012) (84)
Tight bounds on maximal and maximum matchings (2001) (83)
Experiments on Adaptive Set Intersections for Text Retrieval Systems (2001) (80)
Efficient algorithms for Petersen's matching theorem (1999) (79)
Basic network creation games (2010) (79)
When can you fold a map? (2000) (79)
Unfolding some classes of orthogonal polyhedra (1998) (77)
(Non)Existence of Pleated Folds: How Paper Folds Between Creases (2009) (77)
The geometry of binary search trees (2009) (77)
Ununfoldable polyhedra with convex faces (1999) (76)
Recent Results in Computational Origami (2002) (76)
Necklaces, Convolutions, and X+Y (2006) (73)
Origamizer: A Practical Algorithm for Folding Any Polyhedron (2017) (72)
Reconfiguration of list edge-colorings in a graph (2009) (72)
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs (2009) (72)
Resizable Arrays in Optimal Time and Space (1999) (71)
PushPush and Push-1 are NP-hard in 2D (2000) (71)
Classic Nintendo games are (computationally) hard (2012) (69)
Folding Flat Crease Patterns with Thick Materials (2015) (65)
Circle Packing for Origami Design Is Hard (2010) (62)
The Two-Handed Tile Assembly Model is not Intrinsically Universal (2013) (61)
Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality (2005) (61)
Diameter and Treewidth in Minor-Closed Graph Families, Revisited (2004) (60)
Swapping labeled tokens on graphs (2014) (60)
Folding and Cutting Paper (1998) (59)
The Open Problems Project (2007) (59)
Tight bounds for the partial-sums problem (2004) (58)
Contraction decomposition in h-minor-free graphs and algorithmic applications (2011) (57)
The Bidimensional Theory of Bounded-Genus Graphs (2004) (56)
Locked and unlocked polygonal chains in 3D (1998) (55)
Scheduling to minimize gaps and power consumption (2007) (54)
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors (2004) (53)
A Threads-Only MPI Implementation for the Development of Parallel Programs (1997) (52)
Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors (2005) (52)
Folding and unfolding (2002) (52)
Open problems from cccg 2001 (2002) (51)
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs (2009) (51)
Blowing Up Polygonal Linkages (2003) (51)
A Pseudopolynomial Time O (log n )-Approximation Algorithm for Art Gallery Problems (2007) (50)
Rigid origami vertices: conditions and forcing sets (2015) (50)
Shape replication through self-assembly and RNase enzymes (2010) (50)
An end-to-end approach to making self-folded 3D surface shapes by uniform heating (2014) (49)
An energy-driven approach to linkage unfolding (2004) (49)
Efficient Tree Layout in a Multilevel Memory Hierarchy (2002) (49)
The distance geometry of music (2007) (48)
Linear-time algorithm for sliding tokens on trees (2014) (47)
Low-Dimensional Embedding with Extra Information (2004) (46)
A Survey of Folding and Unfolding in Computational Geometry (2007) (46)
Retroactive data structures (2004) (46)
A Distributed boundary detection algorithm for multi-robot systems (2009) (46)
The Stackelberg Minimum Spanning Tree Game (2007) (46)
A linear lower bound on index size for text retrieval (2001) (46)
How to influence people with partial incentives (2014) (46)
A unified access bound on comparison-based dynamic dictionaries (2007) (46)
Locked and Unlocked Polygonal Chains in Three Dimensions (1999) (44)
Planar Embeddings of Graphs with Specified Edge Lengths (2003) (43)
Planning to fold multiple objects from a single self-folding sheet (2011) (43)
Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance (2008) (43)
The price of anarchy in cooperative network creation games (2009) (43)
Curved Crease Folding – a Review on Art, Design and Mathematics (2011) (42)
Linear Reconfiguration of Cube-Style Modular Robots (2007) (42)
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004) (41)
Cache-Oblivious Algorithms and Data Structures (2003) (41)
Geometry and Topology of Polygonal Linkages (2004) (41)
Hinged dissections of polyominoes and polyforms (1999) (40)
Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy (2002) (40)
An O(n^3)-Time Algorithm for Tree Edit Distance (2006) (40)
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch (2018) (39)
The Complexity of Clickomania (2001) (39)
Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) (2010) (38)
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile (2014) (37)
Open problem session (2010) (37)
Optimal Arrangement of Leaves in the Tree Representing Hierarchical Clustering of Gene Expression Data (2001) (37)
Algorithms for Solving Rubik's Cubes (2011) (36)
Reconfiguring Massive Particle Swarms with Limited, Global Control (2013) (36)
What is the optimal shape of a city (2004) (35)
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction (2009) (35)
Constraint Logic: A Uniform Framework for Modeling Computation as Games (2008) (35)
Voronoi game on graphs and its complexity (2006) (35)
Folding and Unfolding Linkages, Paper, and Polyhedra (2000) (35)
Hinged Dissections Exist (2007) (35)
Filling holes in triangular meshes by curve unfolding (2009) (34)
Reconstructing David Huffman’s Legacy in Curved-Crease Folding (2016) (34)
On Streaming and Communication Complexity of the Set Cover Problem (2014) (34)
Pushing blocks is hard (2003) (33)
A note on reconfiguring tree linkages: trees can lock (2002) (33)
Fast , Interactive Origami Simulation using GPU Computation (2018) (33)
Cache-oblivious dynamic dictionaries with update/query tradeoffs (2010) (32)
Communication-Aware Processor Allocation for Supercomputers (2004) (32)
Moving-Baseline Localization (2008) (32)
Folding and one straight cut suffice (1999) (32)
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics (2005) (31)
Continuous foldability of polygonal paper (2004) (31)
An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms (2007) (31)
Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves (2008) (31)
Who Needs Crossings? Hardness of Plane Graph Rigidity (2016) (30)
Fast allocation and deallocation with an improved buddy system (1999) (30)
Innitesimally Locked Self-Touching Linkages with Applications to Locked Trees (2002) (30)
UNO is hard, even for a single player (2010) (30)
Enumerating Foldings and Unfoldings Between Polygons and Polytopes (2001) (29)
Approximability of the subset sum reconfiguration problem (2011) (28)
A Universal Crease Pattern for Folding Orthogonal Shapes (2009) (28)
Dynamic optimality - almost [competitive online binary search tree] (2007) (28)
Classic Nintendo Games are (NP-)Hard (2012) (27)
Geodesic Ham-Sandwich Cuts (2004) (27)
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications (2002) (27)
Representing Trees of Higer Degree (1999) (27)
Minimizing Movement: Fixed-Parameter Tractability (2009) (27)
Reconfiguring convex polygons (2001) (27)
Vertex-unfoldings of simplicial manifolds (2001) (27)
Particle computation: Designing worlds to control robot swarms with only global signals (2014) (27)
Hinged Dissection of Polypolyhedra (2005) (27)
Non-crossing matchings of points with geometric objects (2013) (27)
A Pseudopolynomial Algorithm for Alexandrov's Theorem (2008) (26)
Refolding Planar Polygons (2004) (26)
Decomposition, approximation, and coloring of odd-minor-free graphs (2010) (26)
Long proteins with unique optimal foldings in the H-P model (2002) (26)
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2003) (26)
Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs (2014) (26)
Computational complexity and an integer programming model of Shakashaka (2014) (26)
Efficient Reconfiguration of Lattice-Based Modular Robots (2013) (26)
Covering Points by Disjoint Boxes with Outliers (2009) (26)
Zig-Zag Numberlink is NP-Complete (2014) (26)
An End-to-End Approach to Self-Folding Origami Structures (2018) (25)
Exponential Speedup of Fixed-Parameter Algorithms on K3, 3-Minor-Free or K5-Minor-Free Graphs (2002) (25)
Zipper unfoldings of polyhedral complexes (2010) (25)
Push-2-f is pspace-complete (2002) (25)
Folding Paper Shopping Bags (2006) (25)
Locked and Unlocked Chains of Planar Shapes (2006) (24)
Separating point sets in polygonal environments (2004) (23)
Three Colors Suffice: Conflict-Free Coloring of Planar Graphs (2017) (23)
Pushing blocks is np-complete for noncrossing solution paths (2001) (23)
Folding Any Orthogonal Maze (2009) (23)
Polynomial-Time Algorithm for Sliding Tokens on Trees (2014) (23)
The price of anarchy in network creation games (2012) (23)
The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs (2009) (22)
Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O (1) Glues (2007) (22)
Particle computation: complexity, algorithms, and logic (2017) (22)
Wrapping spheres with flat paper (2009) (22)
Approximability of partitioning graphs with supply and demand (2006) (22)
One-dimensional staged self-assembly (2011) (22)
Solving the Rubik's Cube Optimally is NP-complete (2017) (21)
On reconfiguring tree linkages: Trees can lock (1999) (21)
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction (2008) (21)
PCB ORIGAMI: A MATERIAL-BASED DESIGN APPROACH TO COMPUTER-AIDED FOLDABLE ELECTRONIC DEVICES (2013) (21)
Structural Sparsity of Complex Networks: Random Graph Models and Linear Algorithms (2014) (21)
Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations (2015) (21)
Know When to Fold 'Em: Self-Assembly of Shapes by Folding in Oritatami (2018) (20)
Interpolation search for non-independent data (2004) (20)
Polygons cuttable by a circular saw (2001) (20)
Fun-Sort--or the chaos of unordered binary search (2004) (20)
Reconstructing David Huffman's Origami Tessellations (2013) (20)
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers (2019) (20)
New bounds on optimal binary search trees (2006) (20)
Open Problems: Open Problems from CCCG 2005 (2006) (20)
Proximate point searching (2004) (20)
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction (2006) (20)
Morpion Solitaire (2006) (19)
Coverage with k-transmitters in the presence of obstacles (2010) (19)
Polyhedral Sculptures with Hyperbolic Paraboloids (1999) (19)
Reconfigurable asynchronous logic automata: (RALA) (2010) (19)
Geometric Folding Algorithms: Map Folding (2007) (19)
One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece (2012) (19)
Remarks on Separating Words (2011) (19)
Finding frequent items in sliding windows with multinomially-distributed item frequencies (2004) (19)
Metamorphosis of the cube (1999) (18)
Curved Crease Origami (2008) (18)
Coin-Moving Puzzles (2002) (18)
Computational Complexity of Motion Planning of a Robot through Simple Gadgets (2018) (18)
Lower bounds for asymmetric communication channels and distributed source coding (2006) (18)
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs (2009) (18)
Convexifying Polygons Without Losing Visibilities (2011) (18)
Super Mario Bros. is Harder/Easier Than We Thought (2016) (18)
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques (2003) (17)
Interlocked open linkages with few joints (2002) (17)
-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor (2002) (17)
Edge-guarding Orthogonal Polyhedra (2011) (17)
Common Unfoldings of Polyominoes and Polycubes (2010) (17)
Efficient constant-velocity reconfiguration of crystalline robots** (2011) (17)
New geometric algorithms for fully connected staged self-assembly (2015) (17)
A simplified and dynamic unified structure (2004) (16)
Embedding Stacked Polytopes on a Polynomial-Size Grid (2011) (16)
Flipturning Polygons (2000) (16)
Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm (2011) (16)
Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement (2016) (16)
Edge-unfolding nested polyhedral bands (2008) (16)
07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs (2007) (16)
Robot Localization without Depth Perception (2002) (16)
Convexifying Monotone Polygons (1999) (16)
Quickly deciding minor-closed parameters in general graphs (2007) (15)
On Rolling Cube Puzzles (2007) (15)
PushPush-k is PSPACE-Complete (2004) (15)
On k-convex polygons (2010) (15)
A simple proof that the $(n^2-1)$-puzzle is hard (2017) (14)
Continuously Flattening Polyhedra Using Straight Skeletons (2014) (14)
Continuous Blooming of Convex Polyhedra (2009) (14)
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams (2005) (14)
Sand drawings and Gaussian graphs (2007) (14)
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals (2015) (14)
O(1)-Approximations for Maximum Movement Problems (2011) (14)
Combining Binary Search Trees (2013) (14)
Common Developments of Several Different Orthogonal Boxes (2011) (13)
Geometric Restrictions on Producible Polygonal Protein Chains (2003) (13)
Sequentially Swapping Colored Tokens on Graphs (2017) (13)
Ununfoldable polyhedra (1999) (13)
Games of No Chance 3: Playing games with algorithms: Algorithmic combinatorial game theory (2009) (13)
Flat-State Connectivity of Linkages under Dihedral Motions (2002) (13)
Facet Ordering and Crease Assignment in Uniaxial Bases (2009) (13)
Particle computation: Device fan-out and binary memory (2015) (13)
The Voronoi game on graphs and its complexity (2011) (13)
Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes (2000) (12)
Correction: Basic Network Creation Games (2014) (12)
Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town? (2010) (12)
Palindrome recognition using a multidimensional tape (2003) (12)
Refolding planar polygons (2006) (12)
Universal Hinge Patterns to Fold Orthogonal Shapes (2010) (12)
Balanced k-colorings (2000) (12)
The Computational Complexity of Portal and Other 3D Video Games (2016) (12)
Simple Folding is Really Hard (2017) (12)
Interlocked open and closed linkages with few joints (2003) (12)
Scheduling to minimize power consumption using submodular functions (2010) (11)
Box Pleating is Hard (2015) (11)
JOINING UNFOLDINGS OF 3-D SURFACES (2013) (11)
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting (2016) (11)
PushPush is NP-hard in 2D (1999) (11)
Reaching folded states of a rectangular piece of paper (2001) (11)
Relaxed Gabriel Graphs (2009) (11)
Optimally Adaptive Integration of Univariate Lipschitz Functions (2006) (11)
07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007) (11)
Optimal adaptive algorithms for finding the nearest and farthest point on a parametric black-box curve (2003) (11)
Grid Vertex-Unfolding Orthostacks (2004) (10)
Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising (2010) (10)
Plane Embeddings of Planar Graph Metrics (2006) (10)
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths (2014) (10)
Protocols for non-deterministic communication over synchronous channels (1998) (10)
Tight bounds for dynamic convex hull queries (again) (2007) (10)
Tree-Residue Vertex-Breaking: a new tool for proving hardness (2017) (10)
Optimizing a 2D Function Satisfying Unimodality Properties (2005) (10)
Confluently Persistent Tries for Efficient Version Control (2008) (10)
Cache-Adaptive Analysis (2013) (10)
Edge-Compositions of 3D Surfaces (2013) (10)
A Generalized Carpenter's Rule Theorem for Self-Touching Linkages (2009) (10)
Worst-Case Optimal Tree Layout in a Memory Hierarchy (2004) (10)
Unlocking history through automated virtual unfolding of sealed documents imaged by X-ray microtomography (2021) (10)
Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs (2017) (10)
Realistic Reconfiguration of Crystalline (and Telecube) Robots (2008) (9)
Conic Crease Patterns with Reflecting Rule Lines (2018) (9)
09511 Open Problems - Parameterized complexity and approximation algorithms (2009) (9)
Finding Hidden Independent Sets in Interval Graphs (2003) (9)
Vertex Pops and Popturns (2007) (9)
Fun with fonts: Algorithmic typography (2014) (9)
Puzzles, Art, and Magic with Algorithms (2004) (9)
Algorithms for Designing Pop-Up Cards (2013) (9)
Games on triangulations (2005) (9)
Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces (2016) (9)
Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete (2011) (9)
Worst-Case Optimal Tree Layout in External Memory (2004) (8)
Hiding disks in folded polygons (1998) (8)
Canadians Should Travel Randomly (2014) (8)
C to Java: Converting Pointers into References (1998) (8)
Algorithmic Folding Complexity (2009) (8)
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class (2018) (8)
A Simplified, Dynamic Unified Structure (2004) (8)
Phutball Endgames are Hard (2000) (8)
Rigid Foldability is NP-Hard (2018) (8)
Lossless Fault-Tolerant Data Structures with Additive Overhead (2011) (8)
Generalized D-Forms Have No Spurious Creases (2007) (8)
Conflict-Free Coloring of Graphs (2018) (7)
Folding a paper strip to minimize thickness (2014) (7)
Zero-Area Reciprocal Diagram of Origami (2016) (7)
Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers (2018) (7)
Making Polygons by Simple Folds and One Straight Cut (2010) (7)
Area-Optimal Simple Polygonalizations: The CG Challenge 2019 (2021) (7)
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy (2017) (7)
Cache-Oblivious and Cache-Aware Algorithms (2005) (7)
Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing (2015) (7)
Bidimensionality, Map Graphs, and Grid Minors (2005) (7)
Unfolding polyhedral bands (2004) (7)
Picture-Hanging Puzzles (2012) (7)
Mario Kart Is Hard (2015) (7)
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets (2020) (7)
Algorithmic Graph Minors and Bidimensionality (2008) (7)
A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard (2018) (7)
The Distance Geometry of Deep Rhythms and Scales (2005) (7)
Every Polygon Can Be Untangled (2000) (7)
Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly (2019) (6)
Additive approximation algorithms for list-coloring minor-closed class of graphs (2009) (6)
Minimal Locked Trees (2009) (6)
Reconfiguring Undirected Paths (2019) (6)
Rigid flattening of polyhedra with slits (2015) (6)
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. (2020) (6)
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms (2016) (6)
Matching Points with Things (2010) (6)
Origami, Linkages, and Polyhedra: Folding with Algorithms (2006) (6)
PersiFS: a versioned file system with an efficient representation (2005) (6)
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect (2018) (6)
Higher-Order Concurrency in PVM (1997) (6)
Push-Pull Block Puzzles are Hard (2017) (6)
Kinematics and Dynamics of Nanostructured Origami (2005) (6)
External Memory (2008) (6)
On flat-state connectivity of chains with fixed acute angles (2002) (6)
Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2005) (6)
Computing signed permutations of polygons (2011) (6)
Continuous Flattening of Orthogonal Polyhedra (2015) (6)
Refold rigidity of convex polyhedra (2013) (6)
Single-Player and Two-Player Buttons & Scissors Games - (Extended Abstract) (2015) (6)
Filling Holes in Triangular Meshes Using Digital Images by Curve Unfolding (2010) (6)
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures (2018) (6)
A Generalization of the Source Unfolding of Convex Polyhedra (2011) (5)
Universal Hinge Patterns for Folding Orthogonal Shapes (2010) (5)
Zipper Unfoldability of Domes and Prismoids (2013) (5)
Computing Convex Partitions for Point Sets in the Plane: The CG: SHOP Challenge 2020 (2020) (5)
Tatamibari is NP-complete (2020) (5)
Appendix B: Open problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory (2004) (5)
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete (2020) (5)
18. Clickomania Is Hard, Even with Two Colors and Columns (2017) (5)
Finding Closed Quasigeodesics on Convex Polyhedra (2020) (5)
Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs (2017) (5)
Hinged Dissection of Polygons is Hard (2003) (5)
Reconfigurable Asynchronous Logic Automata (2010) (5)
Characterizing Universal Reconfigurability of Modular Pivoting Robots (2020) (5)
04301 Abstracts Collection - Cache-Oblivious and Cache-Aware Algorithms (2004) (5)
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard (2020) (5)
On universally easy classes for NP-complete problems (2001) (5)
Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121) (2013) (5)
Curves in the Sand: Algorithmic Drawing (2006) (5)
Approximating the Canadian Traveller Problem with Online Randomization (2021) (5)
Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard (2016) (5)
PSPACE-completeness of Pulling Blocks to Reach a Goal (2020) (5)
Finding a Hamiltonian Path in a Cube with Specified Turns is Hard (2013) (5)
Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares (2017) (4)
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible (2018) (4)
Playing Dominoes Is Hard, Except by Yourself (2014) (4)
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs (2012) (4)
Polyhedral Characterization of Reversible Hinged Dissections (2018) (4)
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets (2020) (4)
Approximation Schemes for Planar Graph Problems (2016) (4)
Upward Partitioned Book Embeddings (2017) (4)
Variations on Instant Insanity (2013) (4)
Hardness of Token Swapping on Trees (2021) (4)
Matching regions in the plane using non-crossing segments (2015) (4)
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron (2016) (4)
Folding a Better Checkerboard (2009) (4)
Flattening Fixed-Angle Chains Is Strongly NP-Hard (2011) (4)
Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's" (2013) (4)
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces (2015) (4)
Red-Blue Pebble Game (2018) (4)
NP-completeness of generalized Kaboozle (2010) (4)
Bumpy Pyramid Folding (2014) (4)
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles (2002) (4)
Converting C Pointers to Java References (1998) (4)
Unfolding and dissection of multiple cubes (2016) (4)
Computational complexity of numberless Shakashaka (2015) (4)
Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance (4)
Any monotone boolean function can be realized by interlocked polygons (2010) (4)
ON CURVED CREASES IN ART , DESIGN AND MATHEMATICS (2015) (4)
Cauchy's Arm Lemma on a Growing Sphere (2008) (4)
Folding Equilateral Plane graphs (2011) (3)
Common Development of Prisms, Anti-Prisms, Tetrahedra, and Wedges (2017) (3)
On Wrapping Spheres and Cubes with Rectangular Paper (2013) (3)
Fold-and-Cut Magic (2004) (3)
Constructing Points through Folding and Intersection (2013) (3)
Bounded-degree polyhedronization of point sets (2010) (3)
The Fewest Clues Problem (2016) (3)
Cache-Oblivious Dynamic Dictionaries with Optimal Update / Query Tradeo (2010) (3)
Cookie Clicker (2018) (3)
The complexity of UNO (2010) (3)
ITR : Scalable Location-Aware Monitoring ( SLAM ) Systems (3)
Zipper unfolding of domes and prismoids (2013) (3)
Energy-Eﬃcient Algorithms (2016) (3)
Traversability, Reconfiguration, and Reachability in the Gadget Framework (2022) (3)
Dissection with the Fewest Pieces is Hard, Even to Approximate (2015) (3)
Tetris is NP-hard even with $O(1)$ rows or columns (2020) (3)
Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting (2003) (3)
A Topologically Convex Vertex-Ununfoldable Polyhedron (2011) (3)
First class communication in MPI (1996) (3)
Building Blocks and Excluded Sums (2005) (3)
Dynamic ham-sandwich cuts in the plane (2009) (3)
Narrow misère Dots-and-Boxes (2012) (3)
Folding Polyominoes into (Poly)Cubes (2017) (3)
Computational Balloon Twisting: The Theory of Balloon Polyhedra (2008) (3)
On the effects of hierarchical self-assembly for reducing program-size complexity (2021) (3)
Bidimensional Structures: Algorithms, Combinatorics and Logic (2013) (3)
Games in Particular (2009) (3)
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players (2020) (3)
Revising Quorum Systems for Energy Conservation in Sensor Networks (2007) (3)
Towards Identifying Frequent Items in Sliding Windows (2003) (3)
Degenerative Coordinates in 22.5◦ Grid System (2009) (3)
Filling a Hole in a Crease Pattern: Isometric Mapping from Prescribed Boundary Folding (2014) (3)
Self-Assembly of Arbitrary Shapes with RNA and DNA tiles (extended abstract) (2010) (3)
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares (2021) (3)
Some Polycubes Have No Edge-Unzipping (2019) (3)
Geometric Folding Algorithms: Preface (2007) (3)
Bust-a-Move/Puzzle Bobble Is NP-complete (2015) (3)
Yin-Yang Puzzles are NP-complete (2021) (2)
Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, (2017) (2)
Recursed is not Recursive: A Jarring Result (2020) (2)
PSPACE-Completeness of Reversible Deterministic Systems (2022) (2)
Waiting is not easy but worth it: the online TSP on the line revisited (2019) (2)
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings (2021) (2)
Vertex-Unfoldings of Simplicial Polyhedra (2001) (2)
Cache-Oblivious and Cache-Aware Algorithms, 18.07. - 23.07.2004 (2005) (2)
- ary Clustering with Optimal Leaf Ordering for Gene Expression Data (2)
Virtual Cane Creation for Glassblowers (2015) (2)
The Two-Handed Tile Assembly Model is not Intrinsically Universal (2015) (2)
Polygons Flip Finitely: Flaws and a Fix (2006) (2)
Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves (2009) (2)
The Complexity of Hex and the Jordan Curve Theorem (2016) (2)
Rigid folding analysis of offset crease thick folding (2016) (2)
Folding Polyominoes with Holes into a Cube (2019) (2)
Realizing partitions respecting full and partial order information (2008) (2)
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra (2020) (2)
A Dissimilarity Measure for Comparing Origami Crease Patterns (2015) (2)
Any Monotone Function Is Realized by Interlocked Polygons (2012) (2)
Folding Small Polyominoes into a Unit Cube (2020) (2)
Deflating the Pentagon (2008) (2)
A Novel Routing Algorithm for k-Ary n-Cube Interconnection Networks (1996) (2)
Tangled Tangles (2018) (2)
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers (2021) (2)
Belga B-Trees (2019) (2)
Arithmetic Expression Construction (2020) (2)
Mathematics Is Art (2009) (2)
Folding and Punching Paper (2017) (2)
Negative Instance for the Edge Patrolling Beacon Problem (2020) (2)
Hinged Dissections Exist (2011) (2)
Evaluating the Performance of Parallel Programs in a Pseudo-parallel Mpi Environment (1996) (2)
On Cartesian Trees and Range Minimum Queries (2012) (1)
Six Recipes for Making Polyhedra (2013) (1)
Cache-Oblivious Iterated Predecessor Queries via Range Coalescing (2015) (1)
On the Complexity of Halfspace Volume Queries (2003) (1)
Recognizing Simply Foldable Origami (2007) (1)
TITLE A SYSTEM FOR GENERATING PAPER SLICEFORM ARTWORK (2015) (1)
Algorithm alley: fast and small resizable arrays (2001) (1)
On Dynamic Dictionaries Using Little Space ) (2005) (1)
The complexity of Dyson Telescopes puzzle (2009) (1)
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude (2022) (1)
Approximating the Canadian Traveller Problem with Online Randomization (2021) (1)
Juggling and Card Shuffling Meet Mathematical Fonts (2017) (1)
Existence and hardness of conveyor belts (2019) (1)
Scalable Equilibrium Computation in Multi-agent Influence Games on Networks (2021) (1)
Infinite All-Layers Simple Foldability (2019) (1)
2048 Without Merging (2020) (1)
Games of No Chance 3: The complexity of Dyson Telescopes (2009) (1)
Some Polycubes Have No Edge Zipper Unfolding (2019) (1)
Two-Player Games (2009) (1)
A lifetime of puzzles : a collection of puzzles in honor of Martin Dardner's 90th birthday (2008) (1)
The Constraint-Logic Formalism (2009) (1)
6.890: Algorithmic Lower Bounds: Fun With Hardness Proofs Fall 2014 Lecture 19 Scribe Notes (2014) (1)
Adventures in Maze Folding Art (2020) (1)
Losing at Checkers is Hard (2018) (1)
Meshes Preserving Minimum Feature Size (2012) (1)
Kaboozle Is NP-complete, Even in a Strip (2010) (1)
Particle computation: complexity, algorithms, and logic (2017) (1)
Perspectives on Part II (2009) (1)
Scaling any surface down to any fraction (2015) (1)
Fixed-parameter algorithms for minor-closed graphs ( of locally bounded treewidth ) ? (1)
Session O1: Open Problems and Planning (2000) (1)
Computational Complexity of Arranging Music (2016) (1)
Path Puzzles: Discrete Tomography with a Path Constraint is Hard (2018) (1)
Geometric Folding Algorithms: Rigid Origami and Curved Creases (2007) (1)
Minimal Ununfoldable Polyhedron (2019) (1)
A Locked Orthogonal Tree (2008) (1)
Reconfiguration of Non-crossing Spanning Trees (2022) (1)
Universality Results for Pop-Ups (2011) (1)
Short interlocked linkages (2001) (1)
Minimal forcing sets for 1D origami (2017) (1)
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams (2017) (1)
09511 Abstracts Collection - Parameterized complexity and approximation algorithms (2009) (1)
2 2 D ec 2 00 2 Open Problems from CCCG 2002 (2002) (1)
Parameterized complexity and approximation algorithms Dagstuhl Seminar (2010) (1)
Unfolding Orthogrids with Constant Refinement (2013) (1)
Folding Points to a Point and Lines to a Line (2021) (1)
Reprint of: Refold rigidity of convex polyhedra (2014) (1)
Strings-and-Coins and Nimstring are PSPACE-complete (2021) (1)
Edge-Compositions of 3-D Surfaces (2013) (1)
Form-Finding and Structural Optimization Gaudi Workshop (PDF) (2004) (1)
Reconfiguration of Chains (2007) (1)
Comparative Analysis of Dynamic Graph Techniques and Data Structure (2019) (1)
The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs (2011) (1)
Wrapping the mozartkugel (2007) (1)
Adaptive Protocols for Negotiating Non-Deterministic Choice over Synchronous Channels (1997) (1)
09511 Executive Summary - Parameterized complexity and approximation algorithms (2009) (0)
Computational Complexity of Generalized Push Fight (2018) (0)
MIT Open Access Articles Reconfiguring Undirected Paths (2022) (0)
Fast Dynamic Pointer Following via Link-Cut Trees (2014) (0)
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains (2022) (0)
1 . 3 Level Ancestor ( (2012) (0)
Msn-support Help (2001) (0)
One Complete Straight Cut (2007) (0)
CONFLICT-FREE COLORING OF GRAPHS\ast (2018) (0)
Award Proposal : Data Structures (2008) (0)
Rectangular Spiral Galaxies are Still Hard (2021) (0)
Lecture 22 — 7 May (2007) (0)
Necklaces, Convolutions, and X+Y (2012) (0)
Geometric Folding Algorithms: General Crease Patterns (2007) (0)
Unfolding Polyhedral (2007) (0)
Shortest Paths (2008) (0)
Deterministic Constraint Logic Activation Sequences (2009) (0)
Geometric Folding Algorithms: Silhouettes and Gift Wrapping (2007) (0)
MIT Open Access Articles On Cartesian trees and range minimum queries (2022) (0)
2 Temporal Data Structures (2007) (0)
Invited Talk I Actuator Nets: Folding, Reconfiguring and Deploying Sensors (2009) (0)
Belga B-Trees (2020) (0)
C G ] 2 9 Se p 20 00 On Reconfiguring Tree Linkages : Trees can Lock (2019) (0)
Implementation of a New Algorithm for Sensor Networks Node Localization (2020) (0)
Effcient Simulation of Message-Passing in Distributed-Memory Architectures (1996) (0)
Toward Unfolding Doubly Covered n-Stars (2018) (0)
In the last two lectures, we discussed several data structures for solving predecessor and succes- sor queries in the word RAM model: van Emde Boas trees, y-fast trees, and fusion trees. This establishes an upper bound on the predecessor problem. (2012) (0)
Developing a tetramonohedron with minimum cut length (2022) (0)
Constraint-Logic Quick Reference (2009) (0)
Coverage with k-transmitters in the presence of obstacles (2012) (0)
Ununfoldable polyhedra with 6 vertices or 6 faces (2021) (0)
Dagstuhl-seminar 01121, ''computational Geometry'' Three-dimensional Mesh Generation for Domains with Small Angles a Separation Bound for Real Algebraic Expressions (0)
Problems on Polytope Reconstruction (1999) (0)
Computational-Complexity Reference (2009) (0)
A Demonstration of Tracking the Position of a Moving LEGO Train using the Cricket Indoor Location System (0)
we cover are basic chaining, perfect hashing, linear probing, and cuckoo hashing. (2012) (0)
Controlling Distributed Particle Swarms with only Global Signals (2020) (0)
Expansive Motions for d-Dimensional Open Chains (2011) (0)
Scheduling to minimize gaps and power consumption (2013) (0)
Even $1 \times n$ Edge-Matching and Jigsaw Puzzles are Really Hard (2016) (0)
The cccg 2001 logo (2001) (0)
A Few Lessons I've Learned (2013) (0)
Geometric Folding Algorithms: Reconstruction of Polyhedra (2007) (0)
More than Words : Fonts as Generative Art (2021) (0)
C G ] 3 S ep 2 00 0 PushPush and Push-1 are NP-hard in 2 D (2008) (0)
Minimum feature size preserving decompositions (2009) (0)
Coin-flipping magic (2020) (0)
Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement (2017) (0)
Lecture Beyond Planar Graphs (2011) (0)
Rolling Polyhedra on Tessellations (2022) (0)
Efficient Algorithmic Frameworks via Structural Graph Theory (2016) (0)
Open Problems from Cccg 2002 Kissing Circle Representation (2002) (0)
On the Complexity of Origami Design (2006) (0)
Title Common Developments of Several Different (2011) (0)
C G ] 1 3 Ju n 20 09 Continuous Blooming of Convex Polyhedra (2019) (0)
Computational Geometry: Theory and Applications Dynamic ham-sandwich cuts in the plane ✩ (2009) (0)
One-Player Games (Puzzles) (2009) (0)
Snipperclips: Cutting Tools into Desired Polygons using Themselves (2021) (0)
In the previous lectures we discussed hashing, presenting data structures capable of achieving ex- cellent bounds for solving dictionary and membership problems. The model allowed us to compute hash functions;for instance, the elements can be integers or strings. (2005) (0)
Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? (2010) (0)
Infinite All-Layers Simple Foldability (2019) (0)
RIGID ORIGAMI VERTICES : CONDITIONS AND FORCING (2016) (0)
Covering Folded Shapes (2014) (0)
Dynamic Load Balancing Using Periodically Load Collection with Past Experience Policy on Linux Cluster System (2017) (0)
6.046J / 18.410J Introduction to Algorithms, Fall 2001 (2001) (0)
Geometric Folding Algorithms: Bridging Theory to Practice (2009) (0)
Celeste is PSPACE-hard (2022) (0)
Upper and Lower Bounds (2007) (0)
Complexity of Solo Chess with Unlimited Moves (2023) (0)
Orthogonal Fold & Cut (2022) (0)
Polyhedral Characterization of Reversible Hinged Dissections (2019) (0)
Tile Self-Assembly Simulations (2012) (0)
Geometric Folding Algorithms: Simple Crease Patterns (2007) (0)
ham-sandwich in the plane. (2022) (0)
In this lecture we introduced the topic of range queries with the static range minimum query (RMQ) and lowest common ancestor (LCA) problems. (2005) (0)
6.851 Advanced Data Structures, Spring 2010 (2010) (0)
Basic Network Creation Games Citation (2010) (0)
Framework for Efficient Algorithms in Planar Networks and Beyond (2012) (0)
10091 Abstracts Collection - Data Structures (2004) (0)
Linkage Folding: From Erd˝os to Proteins (2006) (0)
Geometric Folding Algorithms: Edge Unfolding of Polyhedra (2007) (0)
Geometric Folding Algorithms: Folding Polygons to Polyhedra (2007) (0)
New Geometric Algorithms for Staged Self-Assembly (2015) (0)
Notes on “ Logarithmic Lower Bounds in the Cell – Probe Model ” Kevin Zatloukal November 10 , 2010 1 Overview (2010) (0)
Complexity of Reconfiguration in Surface Chemical Reaction Networks (2023) (0)
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases (2021) (0)
Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm (2012) (0)
2 . 1 Vertical Ray Shooting (2012) (0)
In the last lecture we used round elimination to prove lower bounds for the static predecessor problem in the cell probe model. We showed a lower bound of (2005) (0)
Packing Cube Nets into Rectangles with O(1) Holes (2018) (0)
Conflict-Free Coloring of Graphs | SIAM Journal on Discrete Mathematics | Vol. 32, No. 4 | Society for Industrial and Applied Mathematics (2018) (0)
Constraint-Logic Games (2009) (0)
Every Author as First Author (2023) (0)
Approximability of the subset sum reconfiguration problem (2012) (0)
Lower Bounds on Retroactive Data Structures (2022) (0)
Design of Circular-Arc Curved Creases of Constant Fold Angle (2020) (0)
Zero-Player Games (Simulations) (2009) (0)
Regular Paper Simple Folding is Really Hard (2017) (0)
A-025 Finding Reconfigurations between List Edge-Colorings of a Graph (2009) (0)
Without Merging (2020) (0)
Computing Signed Permutations of Polygon (2011) (0)
3 Wilber Bounds (2005) (0)
Computational Complexity of Piano-Hinged Dissections (2013) (0)
Planar Drawings of Origami Polyhedra (1998) (0)
Cookie Clicker (2019) (0)
Geometric Folding Algorithms: Introduction (2007) (0)
A PTAS for Planar Group Steiner Tree via Bootstrapping Approximation (2016) (0)
Regular Paper Folding and Punching Paper (2017) (0)
Geometric Folding Algorithms: Joint-Constrained Motion (2007) (0)
Two Simpli ed Algorithms for MaintainingOrder in a ListMi hael (2002) (0)
Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020, August 5-7, 2020, University of Saskatchewan, Saskatoon, Saskatchewan, Canada (2020) (0)
9. Tangled Tangles (2018) (0)
Games on Triangulations [ Dagstuhl version ] (0)
Dynamic Multithreaded Algorithms (2005) (0)
Approximation Algorithms via Contraction DecompositionA preliminary version of this paper appears in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007 (2010) (0)
Geometric Folding Algorithms: Protein Folding (2007) (0)
Lecture 21 | May 2 (2007) (0)
Approximation algorithms for lasses of graphsex luding single-rossing graphs as minors ? (2007) (0)
Geometric Folding Algorithms: Higher Dimensions (2007) (0)
Impossible Folding Font (2019) (0)
C G ] 2 4 Ja n 20 00 PushPush is NP-hard in 2 D (2008) (0)
Edge-Unfolding Prismatoids: Tall or Rectangular Base (2021) (0)
You Should Be Scared of German Ghost (2015) (0)
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles (2022) (0)
C G ] 8 O ct 1 99 9 Locked and Unlocked Polygonal Chains in 3 D ∗ T . Biedl (2008) (0)
Games in General (2009) (0)
2 Main Section (2014) (0)
Picture-Hanging Puzzles (2013) (0)
D M ] 1 9 M ar 2 01 7 Minimum Forcing Sets for 1 D Origami 1 (2017) (0)
9 GEOMETRY AND TOPOLOGY OF POLYGONAL LINKAGES (2002) (0)
Folding Triangular and Hexagonal Mazes (2017) (0)
Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07. - 13.07.2007 (2007) (0)
Reconfiguring edge-connected pivoting modular robots (2019) (0)
MIT Open Access Articles Canadians Should Travel Randomly (2022) (0)
Minimum Length Barrier to X-rays in a Square (2008) (0)
Inflatable origami-inspired structures (2019) (0)
Folded Structures Satisfying Multiple Conditions (2017) (0)
Design and Control of Nanostructured Origami (2005) (0)
Tribute to Godfried Toussaint (2020) (0)
APPENDIX : Cache-Adaptive Analysis ( Full Version ) (2017) (0)
Problem Classification and Examples (2007) (0)
Shortest Paths and Geodesics (2007) (0)
Path Puzzles: Discrete Tomography with a Path Constraint is Hard (2019) (0)
Resizable Arrays in Optimal Time and (2007) (0)
This Game Is Not Going To Analyze Itself (2023) (0)
Ghost chimneys (2010) (0)
Algorithms Meet Art, Puzzles, and Magic (2009) (0)
Quartering a square optimally (2002) (0)
S anning and Traversing : Maintaining Data forTraversals in a Memory (2002) (0)
Memory Hierarchies and Models of Them (2010) (0)
Geometric Folding Algorithms: Geometric Constructibility (2007) (0)
New Results in Sona Drawing: Hardness and TSP Separation (2020) (0)
Dynamic ham-sandwich cuts in the plane Citation (2009) (0)
Computational geometry column 37 (1999) (0)
Reconstructing points on a circle from labeled distances (2009) (0)
Continuously Flattening Polyhedra Using Straight Skeletons Citation (2014) (0)
Constructing Strings at the Nano Scale via Staged Self-assembly (2011) (0)
Multidimensional Scaling: Approximation and Complexity (2021) (0)
C G ] 11 N ov 1 99 8 Locked and Unlocked Polygonal Chains in 3 D ∗ T . Biedl (2008) (0)
ZHED is NP-complete (2021) (0)
Playing with Triangulations (2002) (0)
Front Matter, Table of Contents, Preface, Conference Organization (2016) (0)
Parallel Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch ∗ (2020) (0)
Escaping a Polygon (2020) (0)
LIPIcs, Volume 49, FUN'16, Complete Volume (2016) (0)
Knapp Lecture Series: Playing with Art and Science: Origami, Glass and Mathematics (2018) (0)
Network Creation Games (2016) (0)
2.1 Description 2.2 Search Operation (2003) (0)
One-dimensional staged self-assembly (2012) (0)
Unfolding Orthotubes with a Dual Hamiltonian Path (2022) (0)
Cache-Oblivious and Cache-Aware Algorithms Dagstuhl Seminar (2005) (0)
Discretization to Prove the Nonexistence of "Small" Common Unfoldings Between Polyhedra (2022) (0)
Last lecture we covered dynamic trees, also known as link-cut trees. Link-cut trees are able to represent a dynamic forest of rooted trees in O(log n) amortized time per operation. (2012) (0)
Contemporary Mathematics All Polygons Flip Finitely (2007) (0)
Blame Trees (2013) (0)
Necklaces , Convolutions , and X + Y Citation (2012) (0)
Geometric Folding Algorithms: Bibliography (2007) (0)
Weaving a uniformly thick sheet from rectangles (2015) (0)
Any platonic solid can transform to another by O(1) refoldings (2023) (0)
Origami Robots and Star Trek Replicators (2012) (0)
Embedding Stacked Polytopes on a Polynomial-Size Grid (2017) (0)
Geometric Folding Algorithms: Planar Linkage Mechanisms (2007) (0)
The 24 th Annual Fall Workshop on Computational Geometry at The University of Connecticut Friday October 31 , 2014 (2014) (0)
In this lecture we discuss the Hamiltonian cycle and path problems, with an emphasis on grid graphs, and use these problems to prove some NP-hardness results for games and lawn mowing. (2014) (0)
Geometric Folding Algorithms: Rigid Frameworks (2007) (0)
Computing 3SAT on a Fold-and-Cut Machine (2017) (0)
Worst-Case Optimal Tree Layout in External Memory (2014) (0)
Geometric Folding Algorithms: The Tree Method (2007) (0)
In this lecture, we consider data structures using close to the information theoretic space. We survey some existing low-space results, including for sux (2005) (0)
Open Problems from ALENEX 2003 (2003) (0)
Survey of Games and Their Complexities (2009) (0)
Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs Dagstuhl Seminar (2007) (0)
Locked Thick Chains (2009) (0)
Paperclip graphs (2019) (0)
Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort (2005) (0)
Paul Erdos Memorial Lecture: Linkage Folding: From Erdos to Proteins (2006) (0)
9. Losing at Checkers Is Hard (2019) (0)
Efficient Origami Construction of Orthogonal Terrains using Cross Section Evolution (2018) (0)
The Legend of Zelda: The Complexity of Mechanics (2022) (0)
Flat Folding a Strip with Parallel or Nonacute Zigzag Creases with Mountain-Valley Assignment (2020) (0)
Programmable Matter Creating Systems that Can Think, Talk, and Morph Autonomously. Phase 2 (2011) (0)
Arboral satisfaction: Recognition and LP approximation (2017) (0)
D ec 2 01 2 Necklaces , Convolutions , and X + (2014) (0)
C C / 0 21 00 20 v 1 2 1 O ct 2 00 2 Tetris is Hard , Even to Approximate (2006) (0)

This paper list is powered by the following services:

Other Resources About Erik Demaine

What Schools Are Affiliated With Erik Demaine?

Erik Demaine is affiliated with the following schools:

Erik Demaine's Academic­Influence.com Rankings