Abstract An Experimental Study of Old and New Depth Measures ∗ (2008)
John Hugg, Eynat Rafalin, Kathryn Seyboth, Diane Souvaine
Data depth is a statistical analysis method that assigns a numeric value to a point based on its centrality relative to a data set. Examples include the half-space depth (also known as Tukey depth),...
A vertex-face assignment for plane graphs (2008)
Diane Souvaine, Csaba D. T'oth
Abstract For any planar straight line graph (Pslg), there is a vertexface assignment such that every vertex is assigned to at most two adjacent faces, and every face is assigned to all its reflex...
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...
Abstract Testing Shortcuts to Maintain Simplicity in Subdivision Simplification (2008)
Craig Falls, Yuanxin Liu, Jack Snoeyink, Diane Souvaine
Cartographers collect more data than they need,and so must simplify coastlines,boundaries,and other linear features to display a map at a given scale. Many simplification methods,however,can...
Eynat Rafalin, Kathryn Seyboth, Diane Souvaine
Proximity graph depth, depth contours, and a new multimodal
Computing the Tool Path of an Externally Monotone Polygon in Linear Time ∗ (2008)
Prosenjit Bose, David Bremner, Diane Souvaine
A Numerically-Controlled (NC) machine typically consists of a worktable and a spindle (or cutter) with several axes of freedom for positioning the tool. In this paper,
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...
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...
Localizing an Object With Finger Probes (2007)
Robert Freimer Samir, Samir Khuller, Christine Piatko, Kathleen Romanik, Diane Souvaine
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger...
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Diane Souvaine, Ileana Streinu, Anja Struyf
computation of location depth contours by methods of combinatorial geometry
Constructing Dierentiable Homeomorphisms between Isomorphic (2007)
Triangulations Frederick Crimins, Frederick Crimins, Diane Souvaine
this paper. 3 Limitations As mentioned in the last section, it is possible to construct a triangle in which one of the edgeperpendiculars drawn from the centroid extends outside the triangle before...
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,...
Constructing Dierentiable Homeomorphisms between Isomorphic (2007)
Triangulations Frederick Crimins, Frederick Crimins, Diane Souvaine
this paper will not be dierentiable at these points. Similar - nite subsets of points with reduced continuity, such as the vertices in a Delauney triangulation, arise in surface interpolation [1, 4,...
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...
Constructing Differentiable Homeomorphisms between Isomorphic (2007)
Triangulations Frederick Crimins, Frederick Crimins, Diane Souvaine
this paper will not be differentiable at these points. Similar finite subsets of points with reduced continuity, such as the vertices in a Delauney triangulation, arise in surface interpolation [1,...
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
An Experimental Study of Old and New Depth Measures (2006)
John Hugg, Eynat Rafalin, Kathryn Seyboth, Diane Souvaine
Data depth is a statistical analysis method that assigns a numeric value to a point based on its centrality relative to a data set. Examples include the half-space depth (also known as Tukey depth),...
An Experimental Study of Old and New Depth Measures (2006)
John Hugg, Eynat Rafalin, Kathryn Seyboth, Diane Souvaine
Data depth is a statistical analysis method that assigns a numeric value to a point based on its centrality relative to a data set. Examples include the half-space depth (also known as Tukey depth),...
Dynamic update of half-space depth contours (2005)
Eynat Rafalin, Diane Souvaine, M. Burr, E. Rafalin, D. L. Souvaine
Planar Minimally Rigid Graphs and Pseudo-Triangulations (2004)
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, ...
Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than π). In this paper we prove that the opposite...
Planar Minimally Rigid Graphs and Pseudo-Triangulations (2003)
Haas, Ruth, Orden, David, Rote, Guenter, Santos, Francisco, Servatius, Brigitte, Servatius, Herman, ...
Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than 180 degrees. In this paper we prove that the opposite...
Planar Minimally Rigid Graphs and Pseudo-Triangulations (2003)
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Hermann Servatius, ...
Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than #). In this paper we prove that the opposite statement is...
Topological Sweep in Degenerate Cases (2002)
Eynat Rafalin Diane, Diane Souvaine, Ileana Streinu
Topological sweep can contribute to efficient implementations of various algorithms for data analysis. Real data, however, has degeneracies. The modification of the topological sweep algorithm...
Topological sweep in degenerate cases (2002)
Eynat Rafalin, Diane Souvaine, Ileana Streinu
Abstract. Topological sweep can contribute to efficient implementations of various algorithms for data analysis.Real data, however, has degeneracies.The modification of the topological sweep...
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...
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...
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...
Efficient Radio Wave Front Propagation for Wireless Radio Signal Prediction (1999)
Due to the ever increasing complexity of wireless network design, wireless network simulation engines have become a necessary tool for wireless network engineers. A signal-strength prediction system...
Constructing Piecewise Linear Homeomorphisms (1997)
Diane Souvaine, Rephael Wenger
Let P = fp 1 ; : : : ; png and Q = fq 1 ; : : : ; q ng be two point sets lying in the interior of rectangles in the plane. We show how to construct a piecewise linear homeomorphism of size O(n 2 )...
Localizing an object with finger probes (1994)
Freimer, Robert, Khuller, Samir, Mitchell, Joe, Piatko, Christine, Romanik, Kathleen, Souvaine, Diane
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger...
Localizing an object with finger probes (1994)
Freimer, Robert, Khuller, Samir, Mitchell, Joe, Piatko, Christine, Romanik, Kathleen, Souvaine, Diane
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger...
Separating Bi-Chromatic Points by Parallel Lines (1994)
Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri
Given a 2-coloring of the vertices of a regular n-gon P , how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that bn=2c is a tight upper bound, and also...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2, given n points in the plane and a tripartition k1 + k2 + k3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains...
On Compatible Triangulations of Simple Polygons (1993)
Boris Aronov, Raimund Seidel, Diane Souvaine
It is well known that, given two simple n-sided polygons, it may not be possible to triangulate the two polygons in a compatible fashion, if one's choice of triangulation vertices is restricted...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2pi, given n points in the plane and a tripartition k 1 + k 2 + k 3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2ß, given n points in the plane and a tripartition k 1 + k 2 + k 3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge...
Separating Bi-Chromatic Points by Parallel Lines (1990)
Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri
Given a 2-coloring of the vertices of a regular n-gon P, how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that ⌊n/2 ⌋ is a tight upper bound, and...