David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán
Abstract. In this paper we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that...
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...
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...
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...
CONSTRAINED QUADRILATERAL MESHES OF BOUNDED SIZE (2008)
Suneeta Ramaswami, Marcelo Siqueira, Tessa Sundaram, Jean Gallier, James Gee
We introduce a new algorithm to convert triangular meshes of polygonal regions, with or without holes, into strictly convex quadrilateral meshes of small bounded size. Our algorithm includes all...
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...
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...
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...
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,...
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...
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...
Experimental Results on Quadrangulations of Sets of Fixed Points (2008)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining “nice ” quadrangulations of planar sets of points. For many applications “nice ” means that the quadrilaterals obtained are convex if possible and as...
Experimental Results on Quadrangulations of Sets of Fixed Points (2008)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
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 ,...
Small Convex Quadrangulations of Point Sets (2008)
David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristan
In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3b 2 c...
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...
Experimental Results on Quadrangulations of Sets of Points (2007)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining "nice" quadrangulations of planar sets of points. For many applications "nice" means that the quadrilaterals obtained are convex if possible...
On Removing Extrinsic Degeneracies in Computational Geometry (2007)
Francisco Gómez, Suneeta Ramaswami, Godfried Toussaint
Existing methods for removing degeneracies in computational geometry can be classified as either approximation or perturbation methods. These methods give the implementer two rather unsatisfactory...
Sanguthevar Rajasekaran, Suneeta Ramaswami, Prof Sanguthevar Rajasekaran
The motion planning problem for an object with two degrees of freedom moving in the plane can be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional mobile...
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...
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
Upper and Lower Bounds for Strictly Convex Quadrilateral Meshes of Point Sets (2007)
David Bremner, Ferran Hurtado, Suneeta Ramaswami
In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3b n 2 c...
Mark De Berg, David Bremner, Suneeta Ramaswami, Gordon Wilfong
We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
Experimental Results on Quadrangulations of Sets of Fixed Points Prosenjit Bose (2007)
Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining "nice " quadrangulations of planar sets of points. For many applications "nice " means that the quadrilaterals obtained are...
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...
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Diane Souvaine, Ileana Streinu, Anja Struyf
computation of location depth contours by methods of combinatorial geometry
Efficient Computation of Location Depth Contours by Methods of Computational Geometry (2007)
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, J. Antoni Sellarès, Diane Souvaine, Ileana Streinu, ...
The concept of location depth was introduced as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust estimation,...
Experimental Results on Upper Bounds for Vertex Pi-Lights (2007)
Victoria Brumberg, Suneeta Ramaswami, Diane Souvaine
The problem of illuminating a simple n-gon with cn, c < 1 #- lights is open, whereas a lower bound of n# is known. We provide an algorithm for placing #-lights, and experimental results that...
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...
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...
Small Strictly Convex Quadrilateral Meshes of Point Sets (2002)
Bremner, David, Hurtado, Ferran, Ramaswami, Suneeta, Sacristan, Vera
In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that...
Fast implementation of depth contours using topological sweep (2001)
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Toni Sellares, Diane Souvaine, Ileana Streinu, ...
The concept of location depth was introduced in statistics as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust...
Improved Approximation Algorithms for Rectangle Tiling and Packing (Extended Abstract) (2001)
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan, Suneeta Ramaswami
) 1 Introduction We study several rectangle tiling and packing problems. These are natural combinatorial problems that arise in many applications in databases, parallel computing and image...
Fast implementation of depth contours using topological sweep (2001)
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Diane Souvaine, Ileana Streinuk, Anja Struyf
1 Introduction The location depth of a given point a relative to a bivariate data set first occurred (without being given a name) as a test statistic of Hodges [8] for the hypothesis that a is the...
Improved Approximation Algorithms for Rectangle Tiling and Packing (2001)
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan, Suneeta Ramaswami
Fast implementation of depth contours using topological sweep (2001)
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Toni Sellarès, Diane Souvaine, Ileana Streinu, ...
The concept of location depth was introduced in statistics as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust...
Experimental results on upper bounds for vertex pi-lights (2001)
Victoria Brumberg, Suneeta Ramaswami, Diane Souvaine
The problem of illuminating a simple n-gon with cn, c < 1 πlights is open, whereas a lower bound of ⌊ 3 5 n ⌋ is known. We provide an algorithm for placing π-lights, and experimental results...
Aichholzer, Oswin, Cortes, Carmen, Demaine, Erik D., Dujmovic, Vida, Erickson, Jeff, Meijer, Henk, ...
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hull edge. Joss and...
Computing Constrained Minimum-Width Annuli of Point Sets (2000)
Mark De Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong
We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
Implicit Convex Polygons (2000)
Francisco Gomez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán, Godfried Toussaint
Convex polygons in the plane can be de ned explicitly as an ordered list of vertices, or given implicitly, for example by a list of linear constraints. The latter representation has been considered...
Implicit Convex Polygons (2000)
Francisco Gómez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán, Godfried Toussaint
this paper we study the case, that appears to be very natural, in which the polygons are given by a set of linear restrictions, i.e. by a possibly redundant intersection of halfplanes. There is not...
On Removing Non-degeneracy Assumptions in Computational Geometry (Extended Abstract) (1997)
Francisco Gómez, Suneeta Ramaswami, Godfried Toussaint
) Francisco G'omez 1 , Suneeta Ramaswami 2 and Godfried Toussaint 2 1 Dept. of Applied Mathematics, Universidad Politecnica de Madrid, Madrid, Spain 2 School of Computer Science, McGill...
Computing Constrained Minimum-Width Annuli of Point Sets (1996)
Mark De Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong
. We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
Converting Triangulations to Quadrangulations (1995)
Suneeta Ramaswami, Pedro Ramos, Godfried Toussaint
We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such...
Converting Triangulations to Quadrangulations (1995)
Suneeta Ramaswami, Pedro Ramos, Godfried Toussaint
We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such...
Voronoi diagrams and algorithmic motion planning: Parallel and randomized techniques (1994)
The ability to manipulate objects in computer graphics and robotics depends critically on fast and feasible solutions to motion planning problems. The central theme of this dissertation is the...
Rajasekaran, Sanguthevar, Ramaswami, Suneeta
In this paper, we present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n non-intersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs...
The problem of algorithmic motion planning is one that has received considerable attention in recent years. The automatic planning of motion for a mobile object moving amongst obstacles is a...
Convex Hulls: Complexity and Applications (A Survey) (1993)
Computational geometry is, in brief, the study of algorithms for geometric problems. Classical study of geometry and geometric objects, however, is not well-suited to efficient algorithms techniques....
Rajasekaran, Sanguthevar, Ramaswami, Suneeta
The motion planning problem for an object with two degrees of freedom moving in the plane can be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional mobile...