Computing the detour and spanning ratio of paths, trees and cycles in 2D and 3D (2008)
Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, ...
The detour and spanning ratio of a graph � embedded in �� � measure how well � approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
Convexifying Polygons in 3D: a Survey (2008)
Michael Soss, Godfried T. Toussaint
To convexify a polygon is to reconfigure it with respect to a given set of operations until the polygon becomes convex. The problem of convexifying polygons has had a long history in a variety of...
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
Simple Polygons that Cannot be Deflated (2007)
Thomas Fevens Mcgill, Thomas Fevens, Antonio Hernandez, Michael Soss
Given a simple polygon in the plane, a deflation is defined as the inverse of a flip in the Erdos-Nagy sense. In 1993 Bernd Wegner conjectured that every simple polygon admits only a finite number of...
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...
Research Proposal Geometric Algorithms for Protein Folding (2007)
The problem of predicting the three-dimensional structure of a protein from its amino acid sequence is one of the most open famous problems in modern biochemistry. Physicists, chemists, biologists,...
Preprocessing Chains for Dihedral Rotations is Difficult (2007)
Michael Soss, Jeff Erickson, Mark Overmars
This draft was last touched on September 14, 2001. We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each...
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...
Geometric and Computational Aspects of Polymer Reconguration (2007)
Michael Soss, Godfried T. Toussaint
We examine a few computational geometric problems concerning the structures of polymers. We use a standard model of a polymer, a polygonal chain (path of line segments) in three dimensions. The chain...
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...
Reconfiguring Polymer-like 3D Linkages (2007)
Michael Soss, Godfried T. Toussaint
We examine a few computational geometric problems concerning the structures of polymers. We use a standard model of a polymer, a polygonal chain (path of line segments) in three dimensions. The chain...
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
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...
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...
Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible (2002)
Soss, Michael, Erickson, Jeff, Overmars, Mark
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Long Proteins with Unique Optimal Foldings in the H-P Model (2002)
Aichholzer, Oswin, Bremner, David, Demaine, Erik D., Meijer, Henk, Sacristán, Vera, Soss, Michael
It is widely accepted that (1) the natural or folded state of proteins is a global energy minimum, and (2) in most cases proteins fold to a unique state determined by their amino acid sequence. The...
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...
Computing the maximum detour and spanning ratio of planar chains, trees and cycles (2002)
Stefan Langerman, Pat Morin, Michael Soss
Let G = (V, E) be an embedded connected graph with n vertices and m edges. Specifically, the vertex set V consists of points in R 2, and E consists
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Je Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Computing the maximum detour and spanning ratio of planar chains, trees and cycles (2002)
Stefan Langerman, Pat Morin, Michael Soss
Abstract. The maximum detour and spanning ratio of an embedded graph G are values that measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we...
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...
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
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...
Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees and Cycles (2002)
Stefan Langerman, Pat Morin, Michael Soss
The maximum detour and spanning ratio of an embedded graph G are values that measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
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...
Simple Polygons with an Infinite Sequence of Deflations (2001)
Thomas Fevens, Antonio Hernandez, Antonio Mesa, Patrick Morin, Michael Soss
Given a simple polygon in the plane, a deflation is defined as the inverse of a flip in the Erdos-Nagy sense. In 1993 Bernd Wegner conjectured that every simple polygon admits only a finite number of...
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...
Convexifying Polygons with Simple Projections (2000)
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...