Cauchy's Arm Lemma on a Growing Sphere (2008)
Abel, Zachary, Charlton, David, Collette, Sebastien, Demaine, Erik D., Demaine, Martin L., Langerman, Stefan, ...
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....
Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues (2008)
Demaine, Erik D., Demaine, Martin L., Fekete, Sandor P., Ishaque, Mashhood, Rafalin, Eynat, Schweller, Robert T., ...
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various...
A Locked Orthogonal Tree (2008)
Charlton, David, Demaine, Erik D., Demaine, Martin L., Price, Gregory, Tu, Yaa-Lirng
We give a counterexample to a conjecture of Poon [Poo06] that any orthogonal tree in two dimensions can always be flattened by a continuous motion that preserves edge lengths and avoids...
Hinged Dissections Exist (2007)
Abbott, Timothy G., Abel, Zachary, Charlton, David, Demaine, Erik D., Demaine, Martin L., Kominers, Scott D.
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...
Generalized D-Forms Have No Spurious Creases (2007)
Price, Gregory N., Demaine, Erik D.
A convex surface flat everywhere but on finitely many disjoint smooth curves (or "seams") and points is called a seam form. We show that the only creases through the flat regions of a seam form are...
The Distance Geometry of Music (2007)
Demaine, Erik D., Gomez-Martin, Francisco, Meijer, Henk, Rappaport, David, Taslakian, Perouz, Toussaint, Godfried T., ...
We demonstrate relationships between the classic Euclidean algorithm and many other fields of study, particularly in the context of music and distance geometry. Specifically, we show how the...
The Stackelberg Minimum Spanning Tree Game (2007)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Newman, Ilan, ...
We consider a one-round two-player network pricing game, the {\em Stackelberg Minimum Spanning Tree} game or StackMST. The game is played on a graph (representing a network), whose edges are colored...
The Helium Stockpile : A Collaboration in Mathematical Folding Sculpture (2006)
Demaine, Erik D., Demaine, Martin L., Palmer, A. Laurie.
Leonardo - Volume 39, Number 3, June 2006
An O(n^3)-Time Algorithm for Tree Edit Distance (2006)
Demaine, Erik D., Mozes, Shay, Rossman, Benjamin, Weimann, Oren
The {\em edit distance} between two ordered trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and...
Locked and Unlocked Chains of Planar Shapes (2006)
Connelly, Robert, Demaine, Erik D., Demaine, Martin L., Fekete, Sandor P., Langerman, Stefan, Mitchell, Joseph S. B., ...
We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid...
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams (2005)
Aronov, Boris, Bose, Prosenjit, Demaine, Erik D., Gudmundsson, Joachim, Iacono, John, Langerman, Stefan, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line l in the...
De Dictionariis Dynamicis Pauco Spatio Utentibus (2005)
Demaine, Erik D., Pagh, Rasmus, Patrascu, Mihai
We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing queries...
Bidimensionality, Map Graphs, and Grid Minors (2005)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial relation between...
Logarithmic Lower Bounds in the Cell-Probe Model (2005)
Patrascu, Mihai, Demaine, Erik D.
We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per operation for several...
Worst-Case Optimal Tree Layout in a Memory Hierarchy (2004)
Demaine, Erik D., Iacono, John, Langerman, Stefan
Consider laying out a fixed-topology tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root...
EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management (2004)
Leong, Ben, Liskov, Barbara, Demaine, Erik D.
EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance...
EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management (2004)
Leong, Ben, Liskov, Barbara, Demaine, Erik D.
EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance...
Communication-Aware Processor Allocation for Supercomputers (2004)
Bender, Michael A., Bunde, David P., Demaine, Erik D., Fekete, Sandor P., Leung, Vitus J., Meijer, Henk, ...
This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The...
Online Searching with Turn Cost (2004)
Demaine, Erik D., Fekete, Sandor P., Gal, Shmuel
We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes...
Unfolding Polyhedral Bands (2004)
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Ileana Streinu, Godfried Toussaint
A band is de ned as the intersection of the surface of a convex polyhedron with the space between two parallel planes, as long as this space does not contain any vertices of the polyhedron. An...
The Bidimensional Theory (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Bidimensionality is a powerful tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper completes the...
Approximation Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Prabhakar Ragde, Dimitrios M. Thilikos
Many problems that are intractable for general graphs allow polynomial-time solutions for structured classes of graphs, such as planar graphs and graphs of bounded treewidth.
Bidimensional Parameters and Local Treewidth (2004)
Erik D. Demaine, Fedorv. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k then the treewidth of the graph is bounded by some function of k. This...
The Bidimensional Theory of Bounded-Genus Graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
Bidimensionality is a powerful tool for developing subexponential fixedparameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper completes the...
Cache-Oblivious B-Trees (2004)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. The data structures are independent of the parameters of the memory hierarchy, e.g., the...
When Can You Fold a Map? (2004)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Cache-Oblivious B-Trees (2004)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
We present dynamic search-tree data structures that perform well in the setting of a hierarchical memory (including various levels of cache, disk, etc.), but do not depend on the number of memory...
Efficient Tree Layout in a Multilevel Memory Hierarchy (2004)
Michael A. Bender, Erik D. Demaine
We consider the problem of laying out a tree or trie in a hierarchical memory, where the tree/trie has a fixed parent/child structure. The goal is to minimize...
What is the Optimal Shape of a City? (2004)
Carl M. Bender, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete
If one de nes the distance between two points as the Manhattan distance (the sum of the horizontal distance along streets and the vertical distance along avenues) then one can de ne a city as being...
When Can You Fold a Map? (2004)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a at folding by a sequence of simple folds?...
Tight Bounds on Maximal and Maximum Matchings (2004)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the...
Low-Dimensional Embedding with Extra Information (2004)
Mihai Badoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
Algorithmica manuscript No. (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter, which includes e.g. planar graphs. This characterization has been used as...
Tetris is Hard, Even to Approximate (2004)
Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
PushPush-k is PSPACE-Complete (2004)
Erik D. Demaine, Michael Homann, Markus Holzer
We prove that a pushing-block puzzle called PushPush-k is Pspace-complete for any fixed k >= 1. In this puzzle, a robot moves on a finite grid. Each grid position is either empty or occupied by a...
Geodesic Ham-Sandwich Cuts (2004)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m+r+b. A ham-sandwich geodesic is a shortest path in P...
Finding Hidden Independent Sets in Interval Graphs (2004)
Therese Biedl, Brona Brejova, Erik D. Demaine, Angele M. Hamel, Alejandro Lopez-ortiz, Tomas Vinar
We design e#cient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which...
Games on Triangulations (2004)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games---constructing, transforming, and marking...
Games on Triangulations (2004)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games --- constructing, transforming, and marking...
Fun-Sort --- Or the Chaos of Unordered (2004)
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n log n). If n...
Planar Embeddings of Graphs with Specified Edge Lengths (2004)
Cabello, Sergio, Demaine, Erik D., Rote, Günter
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory...
Planar Embeddings of Graphs with Specified Edge Lengths (2004)
Cabello, Sergio, Demaine, Erik D., Rote, Günter
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory...
Planar Embeddings of Graphs with Specified Edge Lengths (2004)
Cabello, Sergio, Demaine, Erik D., Rote, Günter
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory...
Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski
where the Previous player has no good move and an one where the Next player has a winning move. The end positions are P-positions and recursively, a position is an if the player to move can move to a...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given con guration of lled squares;...
Geodesic Ham-Sandwich Cuts (2003)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m+ r + b. A ham-sandwich geodesic is a shortest path in P...
Approximation Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors (2003)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos
Many problems that are intractable for general graphs allow polynomial-time solutions for structured classes of graphs, such as planar graphs and graphs of bounded treewidth.
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The (k, r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k,...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We present a fixed parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (can be drawn on the plane with at most one...
1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor (2003)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation...
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications (2003)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
We solve an open problem posed by Eppstein in 1995 [14, 15] and re-enforced by Grohe [16, 17] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local...
Subexponential Parameterized Algorithms on Graphs of Bounded-Genus and H-Minor-Free Graphs (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2 . Our results apply to a broad family of graph problems, called bidimensional problems,...
K-ary Clustering with Optimal Leaf Ordering (2003)
Ziv Bar-joseph, Erik D. Demaine, David K. Giord, Angele M. Hamel, Tommi S. Jaakkola, Nathan Srebro
A major challenge in gene expression analysis is e#ective data organization and visualization. One of the most popular tools for this task is hierarchical clustering. Hierarchical clustering allows a...
Optimal Covering Tours with Turn Costs (2003)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Fekete, Sandor P., Mitchell, Joseph S. B., Sethia, Saurabh
We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified...
When Can You Fold a Map? (2003)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Bidimensional Parameters and Local Treewidth (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function of k....
Fixed-Parameter Algorithms for the (k, r)-Center (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The (k, r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k,...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
We consider a general model for representing and manipulating parametric curves, in which a curve is specified by a black box mapping a parameter value between 0 and 1 to a point in Euclidean...
On the Complexity of Halfspace Volume Queries (2003)
Erik D. Demaine, Je Erickson, Stefan Langerman
Given a polyhedron P in R with n vertices, a halfspace volume query asks for the volume of P H for a given halfspace H . We show that, for d 3, such queries can require# n) operations even if the...
On the Complexity of Halfspace Volume Queries (2003)
Erik D. Demaine, Je Erickson, Stefan Langerman
Given a polyhedron P in R with n vertices, a halfspace volume query asks for the volume of P H for a given halfspace H. We show that, for d 3, such queries can require# n) operations even if the...
Fixed-Parameter Algorithms for Minor-Closed Graphs (of Locally Bounded Treewidth) (2003)
Frick and Grohe [7] showed that for each property that is de nable in rstorder logic, and for each class of minor-closed graphs of locally bounded treewidth, there is an O(n )-time algorithm deciding...
Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2 . Our results apply to a broad family of graph problems, called bidimensional problems,...
Equivalence of Local Treewidth and Linear Local Treewidth And Its Algorithmic (2003)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
We solve an open problem posed by Eppstein in 1995 [16, 17] and re-enforced by Grohe [18, 19] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local...
Erik D. Demaine, Mohammadtaghi Hajiaghayi
We solve an open problem posed by Eppstein in 1995 [16, 17] and re-enforced by Grohe [18, 19] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local...
Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We introduce a new framework for designing xed-parameter algorithms with subexponential running time|2 . Our results apply to a broad family of graph problems, called bidimensional problems, which...
Fixed-Parameter Algorithms for Minor-Closed Graphs (of Locally Bounded Treewidth) (2003)
Frick and Grohe [7] showed that for each property # that is definable in firstorder logic, and for each class of minor-closed graphs of locally bounded treewidth, there is an O(n )-time algorithm...
Playing with Triangulations (2003)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking triangulations....