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...
Abstract Unfolding Manhattan Towers (2008)
We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls in a particular shape class we call Manhattan Towers, to a planar simple orthogonal polygon. The algorithm...
Distributed Spanner Construction in Doubling Metric Spaces * (2008)
Mirela Damian, Saurav Pandit, Sriram Pemmaraju
Abstract This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any ">...
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...
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
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...
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
Localized Spanners for Wireless Networks (2008)
Damian, Mirela, Pemmaraju, Sriram V.
We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G=(V,E) and any e > 0, a (1+e)-spanner for G of maximum degree O(1) and total weight O(w(MST)), where...
Abstract APX-Hardness of Domination Problems in Circle Graphs (2008)
Mirela Damian, Sriram V. Pemmaraju
We show that the problem of finding a minimum dominating set in a circle graph is APXhard: there is a constant δ> 0 such that there is no (1 + δ)-approximation algorithm for the minimum...
Distributed Spanner Construction in Doubling Metric Spaces ∗ (2008)
Mirela Damian, Saurav Pandit, Sriram Pemmaraju
This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any ε> 0, a (1 +...
Efficient Many-To-Many Point Matching in One Dimension (2008)
Justin Colannino, Mirela Damian, Ferran Hurtado, Stefan Langerman, Suneeta Ramaswami, Diane Souvaine, ...
Abstract. Let S and T be two sets of points with total cardinality n. The minimum-cost many-to-many matching problem matches each point in S to at least one point in T and each point in T to at least...
We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n 2) “moves ” between simple polygons. Each move is composed of a sequence of atomic moves...
The problem of wireless localization introduced in [EGS07] asks to place a set of fixed localizers (guards) in the plane so as to enable mobile communication devices to prove that they are inside or...
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...
Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk Meijer, Suneeta Ramaswami, ...
∗ Partially supported by MCYT-FEDER BFM2003-00368, Gen. Cat 2001SGR00224 and Gen. Cat 2005SGR00692
Justin Colannino, Ferran Hurtado, Henk Meijer, Godfried Toussaint, Mirela Damian, John Iacono, ...
The restriction scaffold assignment problem takes as input two finite point sets S and T (with S containing more points than T) and establishes a correspondence between points in S and points in T,...
Distributed Spanner Construction in Doubling Metric Spaces (2008)
Mirela Damian, Saurav P, Sriram Pemmaraju
Abstract. This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any ε> 0, a (1...
CONNECTING POLYGONIZATIONS VIA STRETCHES AND TWANGS (2008)
Abstract. We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n 2) “moves ” between simple polygons. Each move is composed of a sequence of...
1 Introduction Unfolding Well-Separated Orthotrees (2008)
Because of the difficulty of the long-standing open problem of deciding whether every convex polyhedron
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 Unfolding Manhattan Towers (2008)
We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls in a particular shape class we call Manhattan Towers, to a planar simple orthogonal polygon. The algorithm...
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...
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...
Local Approximation Schemes for Topology Control (2008)
Damian, Mirela, Pandit, Saurav, Pemmaraju, Sriram
This paper presents a distributed algorithm on wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a linear size, lightweight,...
A Simple Yao-Yao-Based Spanner of Bounded Degree (2008)
It is a standing open question to decide whether the Yao-Yao structure for unit disk graphs (UDGs) is a length spanner of not. This question is highly relevant to the topology control problem for...
Connecting Polygonizations via Stretches and Twangs (2008)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
Connecting Polygonizations via Stretches and Twangs (2008)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
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
Efficient Many-To-Many Point Matching in One Dimension (2008)
Justin Colannino, Mirela Damian, Ferran Hurtado, Stefan Langerman, Henk Meijer, Diane Souvaine, ...
Appears in Graphs and Combinatorics, vol. 23 (2007), supplement, Computational Geometry and Graph Theory. The Akiyama-Chvatal Festschrift. The original publication is available at...
An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment Problem (2008)
Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk Meijer, Suneeta Ramaswami, ...
The restriction sca#old assignment problem takes as input two finite point sets S and T (with S containing more points than T ) and establishes a correspondence between points in S and points in T ,...
20. Connecting Polygonizations via Stretches and Twangs (2008)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswani, Suneeta
We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
A New Lower Bound on Guard Placement for Wireless Localization (2007)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
The problem of wireless localization asks to place and orient stations in the plane, each of which broadcasts a unique key within a fixed angular range, so that each point in the plane can determine...
Connecting Polygonizations via Stretches and Twangs (2007)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n^2) ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
Unfolding Manhattan Towers (2007)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph
We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls into a particular shape class we call Manhattan Towers, to a nonoverlapping planar orthogonal polygon. The...
Epsilon-Unfolding Orthogonal Polyhedra (2006)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph
An unfolding of a polyhedron is produced by cutting the surface and flattening to a single, connected, planar piece without overlap (except possibly at boundary points). It is a long unsolved problem...
S.: Local Approximation Schemes for Topology Control (2006)
This paper presents a distributed algorithm on wireless adhoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a linear size, lightweight, (1 +...
S.: Local Approximation Schemes for Topology Control (2006)
Mirela Damian, Saurav Pandit, Sriram Pemmaraju
This paper presents a distributed algorithm on wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a linear size, lightweight, (1 +...
S.: Local Approximation Schemes for Topology Control (2006)
This paper presents a distributed algorithm for wireless adhoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a lightweight, linear size, (1 +...
Grid Vertex-Unfolding Orthogonal Polyhedra (2006)
An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid...
Grid Vertex-Unfolding Orthogonal Polyhedra (2006)
An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid...
Grid Vertex-Unfolding Orthogonal Polyhedra (2005)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph
An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a *net*, a connected planar piece with no overlaps. A *grid unfolding* allows additional cuts along...
An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment (2005)
Colannino, Justin, Damian, Mirela, Hurtado, Ferran, Iacono, John, Meijer, Henk, Ramaswami, Suneeta, ...
The assignment problem takes as input two finite point sets S and T and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T, and...
Partitioning Regular Polygons into Circular Pieces II:Nonconvex Partitions (2004)
Damian, Mirela, O'Rourke, Joseph
We explore optimal circular nonconvex partitions of regular k-gons. The circularity of a polygon is measured by its aspect ratio: the ratio of the radii of the smallest circumscribing circle to the...
A Note on Objects Built From Bricks without Corners (2003)
Damian, Mirela, O'Rourke, Joseph
We report a small advance on a question raised by Robertson, Schweitzer, and Wagon in [RSW02]. They constructed a genus-13 polyhedron built from bricks without corners, and asked whether every...
Partitioning Regular Polygons into Circular Pieces I: Convex Partitions (2003)
Damian, Mirela, O'Rourke, Joseph
We explore an instance of the question of partitioning a polygon into pieces, each of which is as ``circular'' as possible, in the sense of having an aspect ratio close to 1. The aspect ratio of a...
The current state and the future directions in air quality modelling (1996)
Gregory R. Carmichael, Adrian S, Florian Potra, Valeriu Damian, Mirela Damian
In this paper the present "state " of air quality modeling (as viewed by the authors) is presented. The focus of the paper will be on the "current "...
Epsilon-Unfolding Orthogonal Polyhedra
Abstract. An unfolding of a polyhedron is produced by cutting the surface and flattening to a single, connected, planar piece without overlap (except possibly at boundary points). It is a long...