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...
Detecting all regular polygons in a point set (2009)
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Iacono, John, Langerman, Stefan
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our...
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...
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...
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...
Where to build a temple, and where to dig to find one (2008)
Greg Aloupis, Jean Cardinal, Sébastien Collette, John Iacono, Stefan Langerman
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We use two different approaches to find regular polygons, depending on their number of edges. Those...
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Hurtado, Ferran, Langerman, Stefan, O'Rourke, Joseph, ...
A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of...
Aloupis, G., and others 1 Algorithms for Computing Geometric Measures of Melodic Similarity (2008)
Greg Aloupis, Thomas Fevens, Antonio Mesa, Yurai Nuñez, Stefan Langerman, Tomomi Matsui, ...
We have all heard numerous melodies, whether they come from commercial jingles, jazz ballads, operatic aria, or any of a variety of different sources. How a human detects similarities in melodies has...
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...
Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman
Abstract. We analyze a new popular video-game called Lumines, which was developed by Sony for the PSP platform. It involves a sequence of bichromatic 2x2 blocks that fall in a grid and must be...
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...
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa
Rappaport k Godfried Toussaint \Lambda Abstract Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle \Theta. We wish to rigidly move one chain so...
Abstract. Several measures of data depth have been proposed, each attempting to maintain certain robustness properties. This paper lists the main approaches known to the computer science community....
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Godfried Toussaint
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
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...
Greg Aloupis, Michael Soss, Godfried Toussaint
Given a nite set of points S, two measures of the depth of a query point with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show...
Greg Aloupis, Michael Soss, Godfried Toussaint
Given a nite set of points S, two measures of the depth of a query point with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show...
Algorithms for Bivariate Medians and a Fermat-Torricelli Problem (2007)
For Lines, Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint
Given a set S of n points in R 2, the Oja depth of a point ` is the sum of the areas of all triangles formed by ` and two elements of S. A point in R 2 with minimum depth is an Oja median. We show...
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...
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...
Algorithms for Computing Geometric Measures of Melodic Similarity (2006)
Aloupis, Greg., Fevens, Thomas., Langerman, Stefan., Mesa, Antonio., Nunez, Yurai., ...
Computer Music Journal - Volume 30, Number 3, Fall 2006
A Lower Bound for Computing Oja Depth (2005)
Let S = {s1,..., sn} be a set of points in the plane. The Oja depth of a query point θ with respect to S is the sum of the areas of all triangles (θ, si, sj). This depth may be computed in O(n log...
Reconfigurations of polygonal structures (2005)
This thesis contains new results on the subject of polygonal structure reconfiguration. Specifically, the types of structures considered here are polygons, polygonal chains, triangulations, and...
Reconfigurations of polygonal structures (2005)
This thesis contains new results on the subject of polygonal structure reconfiguration. Specifically, the types of structures considered here are polygons, polygonal chains, triangulations, and...
Reconfiguring Triangulations with Edge Flips and Point Moves (2004)
Aloupis, Greg, Bose, Prosenjit, Morin, Pat
We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration. We show...
Reconfiguring Triangulations with Edge Flips and Point Moves (2004)
Aloupis, Greg, Bose, Prosenjit, Morin, Pat
We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration. We show...
Reconfiguring Triangulations with Edge Flips and Point Moves (2004)
Aloupis, Greg, Bose, Prosenjit, Morin, Pat
We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration. We show...
Algorithms for Computing Geometric Measures of Melodic Similarity ∗ (2004)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, ...
Consider two orthogonal closed chains on a cylinder. These chains are monotone with respect to the tangential Θ direction. We wish to rigidly move one chain so that the total area between the two is...
Reconfiguring triangulations with edge flips and point moves (2004)
Greg Aloupis, Prosenjit Bose, Pat Morin
Abstract. We examine reconfigurations between triangulations and neartriangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration....
Reconfiguring triangulations with edge flips and point moves (2004)
Greg Aloupis, Prosenjit Bose, Pat Morin
Abstract. We examine reconfigurations between triangulations and neartriangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration....
Reconfiguring triangulations with edge flips and point moves (2004)
Greg Aloupis, Prosenjit Bose, Pat Morin
Abstract. We examine reconfigurations between triangulations and neartriangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration....
Computing a geometric measure of the similarity between two melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle Θ. We wish to rigidly move one chain so that the total area between the two chains is...
More Classes of Stuck Unknotted Hexagons (2003)
Greg Aloupis, Günter Ewald, Godfried Toussaint
Consider a hexagonal unknot with edges of xed length, for which we allow universal joint motions but do not allow edge crossings. We consider the maximum number of embedding classes that any such...
Computing a Geometric Measure of the Similarity between two Melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nunez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states—that is, their embeddings in R 2 without self-intersection—can be connected by a continuous...
On flat-state connectivity of chains with fixed acute angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are “flat-state connected. ” A chain is flatstate connected if it can be reconfigured between any two of its planar...
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Jeff Erickson, Stefan Langerman, Henk Meijer, Mark Overmars, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states--that is, their embeddings in R2 without self-intersection--can be connected by a continuous...
On flat-state connectivity of chains with fixed acute angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are “flat-state connected. ” A chain is flatstate connected if it can be reconfigured between any two of its planar...
On Flat-State Connectivity of Chains with Fixed Acute Angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are "flat-state connected." A chain is flatstate connected if it can be reconfigured between any two of its planar...
Algorithms for Bivariate Medians and a Fermat-Torricelli Problem for Lines (2002)
Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint
Given a set S of n points in R , the Oja depth of a point is the sum of the areas of all triangles formed by and two elements of S. A point in R with minimum depth is an Oja median. We show how an...
Flat-State Connectivity of Linkages under Dihedral Motions (2002)
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...
On computing geometric estimators of location / (2001)
Written for the School of Computer Science.
On computing geometric estimators of location (2001)
Let S be a data set of n points in Rd, and m&d4; be a point in Rd which "best" describes S. Since the term "best" is subjective, there exist several definitions for finding m&d4; . However, it is...
On the computation of the bivariate median and a Fermat-Torricelli problem (2001)
Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint
Given a set S of n points in R 2, the Oja depth of a point ` is the sum of the areas of all triangles formed by ` and two elements of S. A point in R 2 with minimum depth is an Oja median. We show...
On the computation of the bivariate median and a Fermat-Torricelli problem (2001)
Greg Aloupis, Michael Soss, Godfried Toussaint
Two denitions for the median of a set of points S in R 2 are the simplicial median and the Oja median. Both may be used as robust estimators of location. The fastest algorithms to date for computing...
On the computation of the bivariate median and a Fermat-Torricelli problem (2001)
Greg Aloupis, Michael Soss, Godfried Toussaint
Two denitions for the median of a set of points S in R 2 are the simplicial median and the Oja median. Both may be used as robust estimators of location. The fastest algorithms to date for computing...
Lower Bounds for Computing Statistical Depth (2001)
Greg Aloupis, Carmen Cortes, Francisco Gomez, Michael Soss, Godfried Toussaint
Given a finite set of points S, two measures of the depth of a query point ` with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show...
On computing geometric estimators of location (2001)
Let S be a data set of n points in R d, and ˆµ be a point in R d which “best ” describes S. Since the term “best ” is subjective, there exist several definitions for finding ˆµ. However,...
On computing geometric estimators of location (2001)
Let S be a data set of n points in Rd, and m&d4; be a point in Rd which "best" describes S. Since the term "best" is subjective, there exist several definitions for finding m&d4; . However, it is...