A Distributed Boundary Detection Algorithm for Multi-Robot Systems (2009)
James Mclurkin, Erik D. Demaine
Abstract — We describe a distributed boundary detection algorithm suitable for use on multi-robot systems with dynamic network topologies. We assume that each robot has access to its local network...
Optimal covering tours with turn costs (2009)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, S Ándor, P. Fekete, ...
Abstract. 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...
Covering Points by Disjoint Boxes with Outliers (2009)
Ahn, Hee-Kap, Bae, Sang Won, Demaine, Erik D., Demaine, Martin L., Kim, Sang-Sub, Korman, Matias, ...
For a set of n points in the plane, we consider the axis--aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this paper, we consider...
A Universal Crease Pattern for Folding Orthogonal Shapes (2009)
Benbernou, Nadia, Demaine, Erik D., Demaine, Martin L., Ovadya, Aviv
We present a universal crease pattern--known in geometry as the tetrakis tiling and in origami as box pleating--that can fold into any object made up of unit cubes joined face-to-face (polycubes)....
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs (2009)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Newman, Ilan, Weimann, Oren
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07. The game is played on a graph (representing a network), whose edges are colored either...
Minimum feature size preserving decompositions (2009)
Aloupis, Greg, Demaine, Erik D., Demaine, Martin L., Dujmovic, Vida, Iacono, John
The minimum feature size of a crossing-free straight line drawing is the minimum distance between a vertex and a non-incident edge. This quantity measures the resolution needed to display a figure or...
Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves (2009)
Aloupis, Greg, Collette, Sebastien, Demaine, Erik D., Langerman, Stefan, Sacristan, Vera, Wuhrer, Stefanie
We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that...
On the Complexity of Reconfiguration Problems (2009)
Takehiro Ito, Erik D. Demaine, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, ...
Abstract. Reconfiguration problems arise when we wish to find a stepby-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We...
(Non)existence of Pleated Folds: How Paper Folds Between Creases (2009)
Demaine, Erik D., Demaine, Martin L., Hart, Vi, Price, Gregory N., Tachi, Tomohiro
We prove that the pleated hyperbolic paraboloid, a familiar origami model known since 1927, in fact cannot be folded with the standard crease pattern in the standard mathematical model of...
Continuous Blooming of Convex Polyhedra (2009)
Demaine, Erik D., Demaine, Martin L., Hart, Vi, Iacono, John, Langerman, Stefan, O'Rourke, Joseph
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further...
Flipturning Polygons (Extended abstract) (2009)
Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Mark Overmars, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Mahini, Hamid, Zadimoghaddam, Morteza
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost \alpha. Together the agents create a network (a...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
Games on Triangulations (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games—constructing, transforming, and marking...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
1 Introduction Let S be a set of n points in the plane, which we assume to be in general position, i.e., no threepoints of S lie on the same line. A triangulation of S is a simplicial decomposition...
Erik D. Demaine, John Iacono, Stefan Langerman
Abstract. We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present but also in the past. In this new paradigm, called retroactive...
Moving-Baseline Localization (2009)
Jun-geun Park, Erik D. Demaine, Seth Teller
The moving-baseline localization (MBL) problem arises when a group of nodes moves through an environment in which no external coordinate reference is available. When group members cannot see or hear...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Mahini, Hamid, Zadimoghaddam, Morteza
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost α. Together the agents create a...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Mahini, Hamid, Zadimoghaddam, Morteza
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost α. Together the agents create a...
Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, MohammadTaghi, Mahini, Hamid, Zadimoghaddam, Morteza
We analyze the structure of equilibria and the price of anarchy in the family of network creation games considered extensively in the past few years, which attempt to unify the network design and...
A Pseudopolynomial Algorithm for Alexandrov's Theorem (2008)
Kane, Daniel, Price, Gregory N., Demaine, Erik D.
Alexandrov's Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by...
Fast Allocation and Deallocation with an Improved Buddy System ∗ (2008)
Gerth Stølting Brodal, Erik D. Demaine, J. Ian Munro
We propose several modifications to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and deallocates blocks...
Erik D. Demaine, Dion Harmon, John Iacono, Scu Dynamic Optimality, Jacob Holm, Kristian De Lichtenberg, ...
Advanced topics in data structures: bibliography list #3
Erik D. Demaine, Gregory Gutin, Royal Holloway, U. London, Dániel Marx, Ulrike Stege, ...
session of the Seminar on Structure Theory and FPT Algorithmics for Graphs, Digraphs and
The Distance Geometry of Deep Rhythms and Scales (2008)
Erik D. Demaine, Francisco Gomez-martin, Henk Meijer, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, ...
Abstract We characterize which sets of k points chosen from n points spaced evenly around a circle have the property that, for each i = 1, 2,..., k − 1, there is a nonzero distance along the circle...
Optimally Adaptive Integration of Univariate Lipschitz Functions (2008)
Ilya Baran, Erik D. Demaine, Dmitriy A. Katz
We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an additive error of at most ǫ using as few...
Abstract On the Complexity of Halfspace Volume Queries (2008)
Erik D. Demaine, Jeff Erickson, Stefan Langerman
Given a polyhedron P in R d 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...
Efficient Algorithms for Petersen's Matching Theorem (2008)
Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
Erik D. Demaine, Mohammadtaghi Hajiaghayi
The date of receipt and acceptance will be inserted by the editor Abstract Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter,...
Robert Connelly, Sándor P. Fekete, Tu Braunschweig, Erik D. Demaine, ...
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...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Stefan Langerman, Suneeta Ramaswami, ...
Abstract. In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 × 2 × 2...
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s...
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications (2008)
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...
Abstract Interpolation Search for Non-Independent Data (2008)
We define a deterministic metric of “well-behaved data” that enables searching along the lines of interpolation search. Specifically, define ∆ to be the ratio of distances between the farthest...
PUZZLES, ART, AND MAGIC WITH ALGORITHMS (2008)
Erik D. Demaine, Martin L. Demaine
Solving and designing puzzles, creating sculpture and architecture, and inventing magic tricks all lead to fun and interesting algorithmic problems. This paper describes some of our explorations into...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Vertex Pops and Popturns (2008)
Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine
This paper considers transformations of a planar polygon P according to two types of operations. A vertex pop (or a pop) reflects a vertex vi, i ∈ {1,..., n}, across the line through the two...
FINDING A DIVISIBLE PAIR AND A GOOD WOODEN FENCE (2008)
Stelian Ciurea, Erik D. Demaine, Corina E. Pǎtras¸cu
We consider two algorithmic problems arising in the lives of Yogi Bear and Ranger Smith. The first problem is the natural algorithmic version of a classic mathematical result: any (n + 1)subset of...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Abstract Polygons Flip Finitely: Flaws and a Fix (2008)
Erik D. Demaine, Blaise Gassend, Godfried T. Toussaint
Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this as an open problem in 1935, several independent purported proofs have been...
Planar Drawings of Origami Polyhedra (2008)
Erik D. Demaine, Martin L. Demaine
Abstract We present a new infinite class of polyhedra based on a class of origami bases that we have developed. To understand these polyhedra and their underlying bases, we examine drawings of their...
(lat. On Dynamic Dictionaries Using Little Space)? (2008)
De Dictionariis, Dynamicis Pauco, Spatio Utentibus, Erik D. Demaine, Rasmus Pagh
1 Introduction The dictionary is one of the most fundamental data-structural problems in com-puter science. In its basic form, a dictionary allows some form of "lookup " on a set S...
Erik D. Demaine, Stefan Langerman
The date of receipt and acceptance will be inserted by the editor Abstract Fixed-angle polygonal chains in 3D serve as an interesting model of protein backbones. Here we consider such chains produced...
Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory (2008)
Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski
This is list of combinatorial games problems collected at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, organized by the authors. For more unsolved problems in combinatorial...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatl, Vera Sacristán, ...
In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2×2×2 meta-modules. The...
Optimally Adaptive Integration of Univariate Lipschitz Functions (2008)
Ilya Baran, Erik D. Demaine, Dmitriy A. Katz
Abstract. We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an error of at most ǫ using as few...
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding (2008)
1 Introduction Many network systems have an inherent asymmetry be-tween two (or more) classes of devices that leads to
Abstract Polygons Flip Finitely: Flaws and a Fix (2008)
Erik D. Demaine, Blaise Gassend, Godfried T. Toussaint
Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this as an open problem in 1935, several independent purported proofs have been...
Correlation Clustering in General Weighted Graphs (2008)
Erik D. Demaine, Dotan Emanuel, Amos Fiat, Nicole Immorlica
We consider the following general correlation-clustering problem [1]: given a graph with real nonnegative edge weights and a 〈+〉/〈− 〉 edge labeling, partition the vertices into clusters to...
Sliding-coin Puzzles, Erik D. Demaine, Martin L. Demaine
The rest of this section presents several sliding-coin puzzles. 1.1 Triangular Lattice We start with some basic puzzles that are on the triangular lattice in the sense that the center of every coin...
Optimally Adaptive Integration of Univariate LipschitzFunctions (2008)
Ilya Baran, Erik D. Demaine, Artificial Intelligence Laboratory
Abstract. We consider the problem of approximately integrating a Lipschitzfunction f (with a known Lipschitz constant) over an interval. The goal is toachieve an error of at most ffl using as few...
Optimal Covering Tours with Turn Costs Esther M. Arkin \Lambda (2008)
Michael A. Bender, Erik D. Demaine
S'andor P. Fekete x Joseph S. B. Mitchell \Lambda Saurabh Sethia
A unified access bound on comparison-based dynamic dictionaries (2008)
Mihai Bădoiu, Richard Cole, Erik D. Demaine, John Iacono
We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element...
Abstract Polygons Flip Finitely: Flaws and a Fix (2008)
Erik D. Demaine, Blaise Gassend, Godfried T. Toussaint
Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this as an open problem in 1935, several independent purported proofs have been...
Universitat Polit`ecnica de Catalunya Polytechnic University (2008)
Erik D. Demaine, Jeff Erickson
ABSTRACT We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a...
ABSTRACT Low-Dimensional Embedding with Extra Information (2008)
Mihai Bădoiu, 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...
Erik D. Demaine, Martin L. Demaine, Perouz Taslakian, Godfried T. Toussaint
Sand drawings form a part of many cultural artistic traditions. Depending on the part of the world in which they occur, such drawings have different names such as sona, kolam, and Malekula drawings....
Abstract Wrapping the Mozartkugel (2008)
Erik D. Demaine, Martin L. Demaine, John Iacono, Stefan Langerman
We study wrappings of the unit sphere by a piece of paper (or, perhaps more accurately, a piece of foil). Such wrappings differ from standard origami because they require infinitely many...
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton, Jack Zito Two
Advanced topics in data structures: bibliography list on string matching
PushPush-k is PSPACE-Complete (2008)
Erik D. Demaine, Michael Hoffmann, 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...
Abstract Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2008)
Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, ...
We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two nonoverlapping convex polygons in the plane. Given two non-overlapping convex polygons P1 and P2 in the...
Robert Connelly, Erik D. Demaine, Günter Rote
Abstract. Consider a planar linkage, consisting of disjoint polygonal arcs and cycles of rigid bars joined at incident endpoints (polygonal chains), with the property that no cycle surrounds another...
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick
Abstract We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l: : : l + n \Gamma 1], of fixed-size elements, as...
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding (2008)
1 Introduction Many network systems have an inherent asymmetry be-tween two (or more) classes of devices that leads to
Playing with Triangulations (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Stefan Langerman, Suneeta Ramaswami, ...
Abstract. In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 × 2 × 2...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
The field of ethnomathematics is the study of mathematics in the works of art of various cultures [2, 3, 9, 13]. The concepts
Geometric Games on Triangulations Extended Abstract (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Optimally Adaptive Integration of Univariate Lipschitz Functions (2008)
Ilya Baran, Erik D. Demaine, Dmitriy A. Katz
1 Introduction We consider the problem of approximating a definite integral of a univariate Lipschitz function (with knownLipschitz constant) to within ffl using the fewest possible samples. The...
Contemporary Mathematics All Polygons Flip Finitely... Right? (2008)
Erik D. Demaine, Blaise Gassend, Godfried T
Abstract. Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this finiteness as an open problem in 1935, several independent...
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....
Erik D. Demaine, Stefan Langerman
The date of receipt and acceptance will be inserted by the editor Abstract Fixed-angle polygonal chains in 3D serve as an interesting model of protein backbones. Here we consider such chains produced...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
Abstract. We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is...
Optimizing a 2D Function Satisfying Unimodality Properties (2008)
Erik D. Demaine, Stefan Langerman
Abstract. The number of probes needed by the best possible algorithm for locally or globally optimizing a bivariate function varies substantially depending on the assumptions made about the function....
Abstract Minimizing Movement (2008)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Shayan Oveisgharan, Morteza Zadimoghaddam
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The date of receipt and acceptance will be inserted by the editor Abstract We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs...
Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity ∗ (2008)
Erik D. Demaine, Martin L. Demaine
Abstract. We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles are all NP-complete. Furthermore, we show direct equivalences between these three types of puzzles: any...
Hayley N. Iben, James F. O’brien, Erik D. Demaine
The date of receipt and acceptance will be inserted by the editor Abstract This paper describes an algorithm for generating a guaranteed-intersection-free interpolation sequence between any pair of...
Variable-Speed Linear Morphing (2008)
Erik D. Demaine, Jonathan Shewchuk, Anna Lubiw
The following is a list of the problems presented on August
Optimally Adaptive Integration of Univariate Lipschitz Functions (2008)
Ilya Baran, Erik D. Demaine, Dmitriy A. Katz
We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an error of at most ǫ using as few samples of f...
A unified access bound on comparison-based dynamic dictionaries (2008)
Mihai Bădoiu, Richard Cole, Erik D. Demaine, John Iacono
We present a dynamic comparison-based search structure that supports insert, delete, and search within the unified bound. The unified bound specifies that it is quick to access an element that is...
Abstract Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding (2008)
We prove nearly tight lower bounds on the number of rounds of communication required by efficient protocols over asymmetric channels between a server (with high sending capacity) and one or more...
Erik D. Demaine, Gregory Gutin, Royal Holloway, U. London, Dániel Marx, Ulrike Stege, ...
session of the Seminar on Structure Theory and FPT Algorithmics for Graphs, Digraphs and
DOI: 10.1007/s00453-004-1146-6 Representing Trees of Higher Degree 1 (2008)
David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao
Abstract. This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our...
Erik D. Demaine, Stefan Langerman
We advance the study of collections of open linkages in 3space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains...
A Pseudopolynomial Time O(log n)-Approximation Algorithm for Art Gallery Problems (2008)
Ajay Deshp, Taejung Kim, Erik D. Demaine, Sanjay E. Sarma
Abstract. In this paper, we give a O(log copt)-approximation algorithm for the point guard problem where copt is the optimal number of guards. Our algorithm runs in time polynomial in n, the number...
(lat. On Dynamic Dictionaries Using Little Space) ⋆ (2008)
Abstract. 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...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatl, ...
In this paper we propose a novel algorithm for both contracting and expanding cube-style modular robots which reconfigures any given source robot composed of n atoms into any given target robot with...
Low-Dimensional Embedding with Extra (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
(will be inserted by the editor)
C to Java: Converting Pointers into References (2008)
We consider the problem of converting C pointers to the less flexible concept of references. Our main application is converting scientific applications from C to Java. We provide a general method to...
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
Abstract. We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and...
G.2.2 [Mathematics of Computing]: Discrete Mathematics—Graph Theory General Terms Algorithms (2008)
Erik D. Demaine, Jeff Erickson
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along...
Abstract Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2008)
Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, ...
We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two nonoverlapping convex polygons in the plane. Given two non-overlapping convex polygons P1 and P2 in the...
Ziv Bar-joseph, Therese Biedl, Broňa Brejová, Erik D. Demaine, David K. Gifford, Angèle M. Hamel, ...
Abstract. In this paper, we study how to present gene expression data to display similarities by trying to find a linear ordering of genes such that genes with similar expression profiles will be...
ABSTRACT Low-Dimensional Embedding with Extra Information (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammad Taghi, 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...
Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O’brien
The date of receipt and acceptance will be inserted by the editor Abstract We present a new algorithm for unfolding planar polygonal linkages without self-intersection based on following the gradient...
March 25, 2005 8:15 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and
Abstract Interpolation Search for Non-Independent Data (2008)
We define a deterministic metric of “well-behaved data” that enables searching along the lines of interpolation search. Specifically, define ∆ to be the ratio of distances between the farthest...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
On the Complexity of Halfspace Volume Queries (2008)
Erik D. Demaine, Jeff Erickson, Stefan Langerman
Given a polyhedron P in R d 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...
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s...
Scheduling to Minimize Gaps and Power Consumption ABSTRACT (2008)
Erik D. Demaine, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi
This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this...
Erik D. Demaine, Martin L. Demaine, Perouz Taslakian, Godfried T. Toussaint
Sand drawings form a part of many cultural artistic traditions. Depending on the part of the world in which they occur, such drawings have different names such as sona, kolam, and Malekula drawings....
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatl, Suneeta Ramaswami, ...
Abstract. In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 × 2 × 2...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Shayan Oveisgharan, Morteza Zadimoghaddam
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects...
Vertex Pops and Popturns (2008)
Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine
This paper considers transformations of a planar polygon P according to two types of operations. A vertex pop (or a pop) reflects a vertex vi, i ∈ {1,..., n}, across the line through the two...
Optimally Adaptive Integration of Univariate Lipschitz Functions (2008)
Ilya Baran, Erik D. Demaine, Dmitriy A. Katz
We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an error of at most ǫ using as few samples of f...
Optimal Dynamic Video-On-Demand using Adaptive Broadcasting (2008)
Therese Biedl, Erik D. Demaine, Er Golynski, Joseph D. Horton, Ro López-ortiz, Guillaume Poirier, ...
Abstract. We consider the transmission of a movie over a broadcast network to support several viewers who start watching at arbitrary times, after a wait of at most twait minutes. A recent approach...
March 25, 2005 14:14 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and
Abstract Grid Vertex-Unfolding Orthostacks (2008)
Erik D. Demaine, John Iacono, Stefan Langerman
An algorithm was presented in [1] for unfolding orthostacks into one piece without overlap by using arbitrary cuts along the surface. It was conjectured that orthostacks could be unfolded using cuts...
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...
Erik D. Demaine, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi, Morteza Zadimoghaddam
This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this...
ABSTRACT Dedicated to Godfried Toussaint (2008)
Robert Connelly, Erik D. Demaine
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...
Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory (2008)
Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski
This is list of combinatorial games problems collected at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, organized by the authors. For more unsolved problems in combinatorial...
Erik D. Demaine, Dimitrios M. Thilikos
Abstract. We introduce a new framework for designing fixed-parameter algorithms with subexponential running time—2 O( √ k) n O(1). Our results apply to a broad family of graph problems, called...
Abstract Minimizing Movement (2008)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Shayan Oveisgharan, Morteza Zadimoghaddam
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects...
Robert Connelly, Sándor P. Fekete, Tu Braunschweig, Erik D. Demaine, ...
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...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The date of receipt and acceptance will be inserted by the editor Abstract We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0,n) into k subintervals of positive integer lengths ℓ1,...,ℓk such that the lengths satisfy a set of simple constraints of the...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
Abstract. We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is...
Erik D. Demaine, Dimitrios M. Thilikos
A preliminary version of this article appeared in the Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP’03). F. Fomin is supported by Norges...
Games on Triangulations (2008)
Oswin Aichholzer David, 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...
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...
Open Problems in Parameterized and Exact Computation — (2008)
Hans L. Bodlaender, Erik D. Demaine, Michael R. Fellows, Jiong Guo, Danny Hermelin, Daniel Lokshtanov, ...
www.cs.uu.nl
Complexity of Union-Split-Find Problems by (2008)
Katherine Jane Lai, Erik D. Demaine
In this thesis, we investigate various interpretations of the Union-Split-Find problem, an extension of the classic Union-Find problem. In the Union-Split-Find problem, we maintain disjoint sets of...
Creative Commons Attribution–Share Alike License 3.0. (2008)
Gregory Nathan Price, Erik D. Demaine, Nathan Price
Alexandrov’s Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by...
The Bidimensionality Theory and Its Algorithmic Applications (2008)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensionality. This theory characterizes a broad range of graph problems (‘bidimensional’) that admit efficient approximate or fixed-parameter solutions in a...
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...
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia
S. Skiena y The easiest way to refold a road map is differently.--- Jones's Rule of the Road (M. Gardner [3]) 1
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...
Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, ...
. While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
Converting C pointers to Java references (2007)
We consider the problem of converting C pointers to the less exible concept of references. Our main application is converting scientific applications from C to Java. We provide a general method to...
Open Problems on Polytope Reconstruction (2007)
Erik D. Demaine, Jeff Erickson
. We describe some open algorithmic problems related to constructing 3-dimensional polytopes from limited information. Introduction. There are several dierent ways to specify convex polytopes in...
Erik D. Demaine, 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 single...
excluding single-crossing graphs as minors (2007)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Prabhakar Ragde, Dimitrios M. Thilikos
algorithms for classes of graphs
Playing with Triangulations (2007)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
More Games of No Chance MSRI Publications (2007)
Erik D. Demaine, Martin L. Demaine, David Eppstein
Abstract. We show that, in John Conway’s board game Phutball (or Philosopher’s Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In...
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?...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos
graphs as minors
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
G.2.2 [Mathematics of Computing]: Discrete Mathematics—Graph Theory General Terms Algorithms (2007)
Erik D. Demaine, Jeff Erickson
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Abstract. Clobber is a new two-player board game. In this paper, we introduce the 1-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by...
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, J. Ian Munro
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3;3 as a minor in time O(3 6
Lars Arge, Michael A. Bender, Erik D. Demaine, J. Ian Munro
In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O( 1 B log M=B
Therese C. Biedl, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
Therese C. Biedl, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. 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...
Oswin Aichholzerf, Vida Dujmovid, Mark Overmars, Carmen Cortes, Jeff Erickson, ...
jeffecs.uiuc.edu
Flipturning Polygons* (Extended abstract) (2007)
Oswin Aichholzer, Carmen Corts, Erik D. Demaine, Vida Dujmovi, Jeff Ericksonll, Henk Meijer, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a xed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3;3 as a minor in time O(3 6
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
Given a planar polygon (or chain) with a list of edges
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
Given a planar polygon (or chain) with a list of edges fe 1; e 2; e 3; : : :; e n 1; e n g, we examine the eect of several operations that permute this edge list, resulting in the formation of a new...
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
We prove that there is a polyhedron with genus 6 whose faces are orthogonal polygons (equivalently, rectangles) and yet the angles between some faces are not multiples of 90, so the polyhedron itself...
Therese Biedl, Erik D. Demaine, Angele M. Hamel
We design ecient competitive algorithms for discovering information hidden by an adversary. Specically, consider a game in a given interval graph G in which the adversary chooses an independent set X...
Cenek Timothy, M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, ...
While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
Erik D. Demaine, Martin L. Demaine, Anna Lubiw
The logo for CCCG this year is in fact an origami crease pattern, with the property that if you fold it at, all the bold lines outlining the letters line up, so
Oswin Aichholzer, Erik D. Demaine, Je Erickson, Ferran Hurtado, Mark Overmars, Michael Soss, ...
We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang
b;1
Oswin Aichholzer, David Bremner, Erik D. Demaine, Henk Meijer, Michael Soss
We explore a problem suggested by Brian Hayes in 1998: what proteins in the twodimensional hydrophilic-hydrophobic (H-P) model have unique optimal foldings? In particular, we prove that there are...
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss
Abstract. This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone...
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?...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
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...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
We give the rst 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...
Robert Connelly, Erik D. Demaine
The line numbers in the margins should encourage you to quickly report any errors that you spot to the authors. Remarks of any other kind are equally welcome. (If you don't like those numbers,...
Unfolding Polyhedral Bands (2007)
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, ...
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...
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2007)
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,...
Flat-State Connectivity of Linkages under Dihedral Motions (2007)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
When Can You Fold a Map? (2007)
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?...
On the Complexity of Halfspace Volume Queries (2007)
Erik Demaine Je, 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 (2007)
Erik D. Demaine, Jeff 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...
ary Clustering with Optimal Leaf Ordering (2007)
For Gene Expression, Ziv Bar-joseph, Erik D. Demaine, David K. Gifford, Nathan Srebro, Angèle M. Hamel, ...
Motivation: A major challenge in gene expression analysis is effective data organization and visualization. One of the most popular tools for this task is hierarchical clustering. Hierarchical...
Tetris is Hard, Even to Approximate (2007)
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...
When Can You Fold a Map? (2007)
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?...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos
graphs as minors
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....
Erik D. Demaine, Mohammadtaghi Hajiaghayi
The date of receipt and acceptance will be inserted by the editor Abstract Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter,...
Geodesic Ham-Sandwich Cuts (2007)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, ...
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...
When Can You Fold a Map? (2007)
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?...
Fun-Sort --- Or the Chaos of Unordered (2007)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
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...
Open Problems At, 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...
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 Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
Approximation algorithms via contraction decomposition (2007)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Bojan Mohar
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Stefan Langerman, Ilan Newman, Oren Weimann
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms (2007)
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers,...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
The price of anarchy in network creation games (2007)
We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game we have a set of selfish node players, each...
Approximation algorithms via contraction decomposition (2007)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Bojan Mohar
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
On rolling cube puzzles (2007)
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-khechen, Sándor P. Fekete, ...
We analyze the computational complexity of various rolling cube puzzles. 1
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
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 (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
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 ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
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 ℓ in the...
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max...
Certified by.......................................................... (2006)
Robert Aubrey Hearn, Erik D. Demaine, Aubrey Hearn
There is a fundamental connection between the notions of game and of computation. At its most basic level, this is implied by any game complexity result, but the connection is deeper than this. One...
Combination Can Be Hard: Approximability of the Unique Coverage Problem (2006)
Erik D. Demaine, Uriel Feige, Mohammadtaghi Hajiaghayi, Mohammad R. Salavatipour
Abstract We prove semi-logarithmic inapproximability for a maximization problem called unique coverage:given a collection of sets, find a subcollection that maximizes the number of elements covered...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine
In the process of developing the second data structure, we develop a new representation of nearest-point and farthest-point Voronoi diagrams of points in convex position. This representation supports...
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, ...
Input: Let P ∈ � d be a set of points lying in convex position. Also given are a point p ∈ P and a halfspace ˆ h ∈ � d. Output: The point q ∈ P which is farthest from p in the halfspace,...
Approximability of partitioning graphs with supply and demand (2006)
Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki
1 Introduction Consider a graph G such that each vertex is either a supply vertex or a de-mand vertex. Each vertex v is assigned a positive real number; the number iscalled the supply of v if v is a...
Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman
We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most...
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
Abstract We explore three important avenues of research in algorithmic graph-minor theory, whichall stem from a key min-max relation between the treewidth of a graph and its largest grid
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
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 ℓ in the...
Locked and unlocked chains of planar shapes (2006)
Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, ...
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...
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
Abstract. We explore the three main avenues of research still unsolved in the algorithmic graph-minor theory literature, which all stem from a key min-max relation between the treewidth of a graph...
Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman
We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most...
Accepted to SIAM Journal on Computing (2006)
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holl
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in O ( 1 B logM/B N B) amortized memory transfers, where M and B are the...
Locked and unlocked chains of planar shapes (2006)
Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor Fekete, Stefan Langerman, ...
If we attach to each bar in a polygonal chain a rigid shape whose inward normals all hit the attached bar, and the resulting hinged chain of shapes does not overlap itself, then this chain can always...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. 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...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
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 ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. 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...
Approximability of partitioning graphs with supply and demand (2006)
Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki
Abstract. Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive...
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...
The bidimensionality Theory and Its Algorithmic Applications (2005)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
This paper surveys the theory of bidimensionality. This theory characterizes a broad range of graph problems (‘bidimensional’) that admit efficient approximate or fixed-parameter solutions in a...
(lat. On Dynamic Dictionaries Using Little Space) (2005)
Erik D. Demaine, De Dictionariis, Dynamicis Pauco, Spatio Utentibus, U. Paderborn, ...
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...
Mobile-assisted localization in wireless sensor networks (2005)
Nissanka B. Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth Teller
Abstract — The localization problem is to determine an assignment of coordinates to nodes in a wireless ad-hoc or sensor network that is consistent with measured pairwise node distances. Most...
Article Type Communicated by Submitted Revised (2005)
Sergio Cabello, Erik D. Demaine, Günter Rote
We consider the problem of finding a planar straight-line embedding of a graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K3;3 as a minor in time O(416:5 pk nO(1)), which is an...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Hinged dissection of polypolyhedra (2005)
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine
Fig. 1. Hinged dissection ofsquare and equilateral triangle [8]. Different shades showdifferent folded states.
Subquadratic algorithms for 3SUM (2005)
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of O(n 2 / max { w lg 2 w, lg 2 n (lg lg n)...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Erik D. Demaine, Martin Farach-colton, Anastasios Sidiropoulos
Abstract. We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is...
Hinged dissection of polyominoes and polyforms (2005)
Erik D. Demaine, Martin L. Demaine, Greg N. Frederickson, Erich Friedman
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Or P. Fekete, Vitus J. Leung, Henk Meijer, ...
1
(lat. On Dynamic Dictionaries Using Little Space) (2005)
De Dictionariis, Dynamicis Pauco, Spatio Utentibus, Erik D. Demaine, Rasmus Pagh, ...
Abstract We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, upto constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing...
Subquadratic algorithms for 3SUM (2005)
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of O(n 2 / max { w lg 2 w, lg 2 n (lg lg n)...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
Abstract. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of...
Subquadratic algorithms for 3SUM (2005)
Abstract. We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of O(n 2 / max { w lg2 w, lg 2 n...
The bidimensionality Theory and Its Algorithmic Applications (2005)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
doi:10.1093/comjnl/bxh000
Hinged dissection of polyominoes and polyforms (2005)
Erik D. Demaine, Martin L. Demaine, Erich Friedman Z
This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is de ned generally...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
Abstract. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of...
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring (2005)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
At the core of the seminal Graph Minor Theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph...
Hinged dissection of polypolyhedra (2005)
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine
Abstract. This paper presents a general family of 3D hinged dissections for polypolyhedra, i.e., connected 3D solids formed by joining several rigid copies of the same polyhedron along identical...
Deploying sensor networks with guaranteed capacity and fault tolerance (2005)
Jonathan L. Bredin, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Daniela Rus
We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously...
Hinged dissection of polyominoes and polyforms (2005)
Erik D. Demaine, Martin L. Demaine, Erich Friedman Z
This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is de ned generally...
The Bidimensionality Theory (2005)
Mohammadtaghi Hajiaghayi, Erik D. Demaine, Mohammadtaghi Hajiaghayi
newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixed-parameter algorithms and approximation algorithms for NPhard graph problems in broad...
Mobile-assisted localization in wireless sensor networks (2005)
Nissanka B. Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth Teller
Abstract — The localization problem is to determine an assignment of coordinates to nodes in a wireless ad-hoc or sensor network that is consistent with measured pairwise node distances. Most...
Mobile-assisted localization in wireless sensor networks (2005)
Nissanka B. Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth Teller
Abstract — The localization problem is to determine an assignment of coordinates to nodes in a wireless ad-hoc or sensor network that is consistent with measured pairwise node distances. Most...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
Abstract. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of...
Computing With Strategic Agents (2005)
Nicole Immorlica, Erik D. Demaine
This dissertation studies mechanism design for various combinatorial problems in the presence of strategic agents. A mechanism is an algorithm for allocating a resource among a group of participants,...
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...
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...