Flexibility of Subdivided Polyhedral Complexes (2009)
A subdivided polyhedron is the graph obtained by adding vertices on some of the edges of the 1-skeleton of a polyhedron. We also consider subdivided polyhedral complexes, which are collections of...
Singularities of Hinge Structures (2008)
Borcea, Ciprian S., Streinu, Ileana
Motivated by the hinge structure present in protein chains and other molecular conformations, we study the singularities of certain maps associated to body-and-hinge and panel-and-hinge chains. These...
Extremal Configurations of Hinge Structures (2008)
Borcea, Ciprian S., Streinu, Ileana
We study body-and-hinge and panel-and-hinge chains in R^d, with two marked points: one on the first body, the other on the last. For a general chain, the squared distance between the marked points...
2
Contemporary Mathematics Pseudo-Triangulations — a Survey (2008)
Günter Rote, Francisco Santos, Ileana Streinu
Abstract. A pseudo-triangle is a simple polygon with exactly three convex vertices, and a pseudo-triangulation is a face-to-face tiling of a planar region into pseudo-triangles. Pseudo-triangulations...
Graded Sparse Graphs and Matroids 1 (2008)
Audrey Lee, Ileana Streinu, Louis Theran
Abstract: Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of some families of generic minimally rigid structures. We define...
Abstract The slider-pinning problem (2008)
Audrey Lee, Ileana Streinu, Louis Theran
A Laman mechanism is a flexible planar bar-and-joint framework with m ≤ 2n − 3 edges and exactly k = 2n − m degrees of freedom. The slider-pinning problem is to eliminate all the degrees of...
Abstract Finding and Maintaining Rigid Components (2008)
Audrey Lee, Ileana Streinu, Louis Theran
We give the first complete analysis that the complexity of finding and maintaining rigid components of planar bar-and-joint frameworks and arbitrary d-dimensional body-and-bar frameworks, using a...
Enumeration of Optimal Pin-Jointed Bistable Compliant Mechanisms (2008)
Naoki Katoh, Makoto Ohsaki, Takuya Kinoshita, Shin-ichi Tanigawa, David Avis, Ileana Streinu
Recently, a new type of mechanism called compliant mechanism has been developed and applied mainly in the field of micro-mechanics. A compliant mechanism has flexible parts to stabilize the...
Contemporary Mathematics Pseudo-Triangulations — a Survey (2008)
Günter Rote, Francisco Santos, Ileana Streinu
Abstract. A pseudo-triangle is a simple polygon with exactly three convex vertices, and a pseudo-triangulation is a face-to-face tiling of a planar region into pseudo-triangles. Pseudo-triangulations...
Abstract. One-degree-of-freedom mechanisms induced by minimum pseudotriangulations with one convex hull edge removed have been recently introduced by the author to solve a family of non-colliding...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured...
Ciprian Borcea, Ileana Streinu
Abstract. Rigid frameworks in some Euclidean space are embedded graphs having a unique local realization (up to Euclidean motions) for the given edge lengths, although globally they may have several....
Contemporary Mathematics Pseudo-Triangulations — a Survey (2008)
Günter Rote, Francisco Santos, Ileana Streinu
Abstract. A pseudo-triangle is a simple polygon with exactly three convex vertices, and a pseudo-triangulation is a face-to-face tiling of a planar region into pseudo-triangles. Pseudo-triangulations...
Enumerating constrained non-crossing minimally rigid frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Combinatorial Genericity and Minimal Rigidity (2007)
Streinu, Ileana, Theran, Louis
A well studied geometric problem, with applications ranging from molecular structure determination to sensor networks, asks for the reconstruction of a set P of n unknown points from a finite set of...
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Hamiltonicity and Colorings of Arrangement Graphs (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical)...
Arrangements of Geometric Objects (2007)
INTRODUCTION A wide range of applied fields (Statistics, Computer Graphics, Robotics, Geographical Databases) depend on solutions to geometric problems: polygon intersection, visibility computations,...
Separation Of Lines, William Steiger, Ileana Streinu
this paper we give an algorithmic-type of separation for these two classes via the complexity of sorting the elements of S, the x-coordinates
Hamiltonicity and Colorings of Geometric Graphs (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (aÆne or projective) and pseudocircle (spherical)...
Francisco Santos, Ileana Streinu
The line numbers in the margins should encourage you to quickly report any errors that you spot to the authors. Remarks of any other kind are equally welcome. (If you don't like those numbers,...
Günter Rote, Francisco Santos, Ileana Streinu
We introduce the polytope of pointed pseudo-triangulations, defined as the polytope of expansive motions of a planar point set subject to certain constraints on the increase of their distances. Its...
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Diane Souvaine, Ileana Streinu, Anja Struyf
computation of location depth contours by methods of combinatorial geometry
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...
Roadmaps in Configuration Spaces of Simple Planar Polygons (2007)
One-degree-of-freedom mechanisms induced by minimum pseudo-triangulations with one convex hull edge removed have been recently introduced by the author to solve a family of non-colliding motion...
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,...
Combinatorial and Algorithmic Volume Rigidity (2007)
Streinu, Ileana, Theran, Louis
This paper has been withdrawn by the authors.
Graded Sparse Graphs and Matroids (2007)
Lee, Audrey, Streinu, Ileana, Theran, Louis
Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called {\bf graded...
Characterizing Sparse Graphs by Map Decompositions (2007)
Haas, Ruth, Lee, Audrey, Streinu, Ileana, Theran, Louis
A {\bf map} is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into $k$ edge-disjoint maps after: (1)...
Sparsity-certifying Graph Decompositions (2007)
Streinu, Ileana, Theran, Louis
We describe a new algorithm, the $(k,\ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,\ell)$-sparse graphs and algorithmic solutions to a family of problems...
Sparse Hypergraphs and Pebble Game Algorithms (2007)
Streinu, Ileana, Theran, Louis
A hypergraph $G=(V,E)$ is $(k,\ell)$-sparse if no subset $V'\subset V$ spans more than $k|V'|-\ell$ hyperedges. We characterize $(k,\ell)$-sparse hypergraphs in terms of graph theoretic, matroidal...
Pebble Game Algorithms and Sparse Graphs (2007)
A multi-graph $G$ on $n$ vertices is $(k,\ell)$-sparse if every subset of $n'\leq n$ vertices spans at most $kn'- \ell$ edges. $G$ is {\em tight} if, in addition, it has exactly $kn - \ell$ edges....
Enumerating non-crossing minimally rigid frameworks (2007)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Pseudo-Triangulations - a Survey (2006)
Rote, Guenter, Santos, Francisco, Streinu, Ileana
A pseudo-triangle is a simple polygon with three convex vertices, and a pseudo-triangulation is a face-to-face tiling of a planar region into pseudo-triangles. Pseudo-triangulations appear as data...
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2006)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also called constrained...
Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs (2006)
We study parallel redrawing graphs: graphs embedded on moving point sets in such a way that edges maintain their slopes all throughout the motion. The configuration space of such a graph is of an...
Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs (2006)
We study parallel redrawing graphs: graphs embedded on moving point sets in such a way that edges maintain their slopes all throughout the motion. The configuration space of such a graph is of an...
Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs (2006)
We study parallel redrawing graphs: graphs embedded on moving point sets in such a way that edges maintain their slopes all throughout the motion. The configuration space of such a graph is of an...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Motivated by the work of Kawamoto et al. [5], who first suggested the use of graph enumeration techniques as an engineering tool for finding an optimum mechanism design, we give an algorithm for...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Abstract. We present an algorithm for enumerating without repetitions all the planar (noncrossing) minimally rigid (Laman) graphs embedded on a given generic set of n points. Our algorithm is based...
Pseudo-triangulations, rigidity and motion planning (2005)
Abstract We propose a combinatorial approach to planning non-colliding trajectories for a polyg-onal bar-and-joint framework with n vertices. It is based on a new class of simple motionsinduced by...
A methodology for efficiently sampling the conformation space of molecular structures (2005)
Audrey Lee, Oliver Brock, Ileana Streinu
Motivated by recently developed computational techniques for studying protein flexibility, and their potential applications in docking, we propose an efficient method for sampling the conformational...
Pebble game algorithms and (k, l)-sparse graphs. Accepted to EuroComb ’05 (2005)
A multi-graph G on n vertices is (k, l)-sparse if every subset of n ′ ≤ n vertices spans at most kn ′ − l edges, 0 ≤ l < 2k. G is tight if, in addition, it has exactly kn − l edges. We...
Single-vertex origami and spherical expansive motions (2004)
Ileana Streinu, Walter Whiteley
Abstract. We prove that all single-vertex origami shapes are reachable from the open flat state via simple, non-crossing motions. We also consider conical paper, where the total sum of the cone...
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...
Expansive motions and the polytope of pointed pseudo-triangulations (2003)
Günter Rote, Francisco Santos, Ileana Streinu
We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on the...
Expansive motions and the polytope of pointed pseudo-triangulations (2003)
Gunter Rote, Francisco Santos, Ileana Streinu
We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on the...
Expansive motions and the polytope of pointed pseudo-triangulations (2003)
Francisco Santos, Ileana Streinu
We introduce the polytope of pointed pseudo-triangulations, dened as the polytope of expansive motions of a planar point set subject to certain constraints on the increase of their distances. Its...
The Zigzag Path of a Pseudo-Triangulation (2003)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudo-triangulation zigzag path allows us to use divide-and-conquer type...
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...
The Zigzag Path of a Pseudo-Triangulation (2003)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
Abstract. We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudotriangulation zigzag path allows us to use...
Singularities of hinge structures (2003)
Ciprian S. Borcea, Ileana Streinu
Motivated by the hinge structure present in protein chains and other molecular conformations, we study the singularities of certain maps associated to body-andhinge and panel-and-hinge chains. These...
Proximate point location (2003)
The following is a list of the problems presented on
The Zigzag Path of a Pseudo-Triangulation (2003)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
Abstract. We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudotriangulation zigzag path allows us to use...
A Topological Representation Theorem for Oriented Matroids (2002)
Bokowski, Juergen, King, Simon, Mock, Susanne, Streinu, Ileana
We present a new direct proof of a topological representation theorem for oriented matroids in the general rank case. Our proof is based on an earlier rank 3 version. It uses hyperline sequences and...
On the Number of Embeddings of Minimally Rigid Graphs (2002)
Borcea, Ciprian, Streinu, Ileana
Rigid frameworks in some Euclidian space are embedded graphs having a unique local realization (up to Euclidian motions) for the given edge lengths, although globally they may have several. We study...
Expansive Motions and the Polytope of Pointed Pseudo-Triangulations (2002)
Rote, Guenter, Santos, Francisco, Streinu, Ileana
We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on the...
Camera Position Reconstruction and Tight Direction Networks (2002)
A concrete reconstruction problem arising in Computer Vision motivates our investigation of combinatorial variations on the problem of drawing a graph with given direction vectors associated to its...
Camera Position Reconstruction and Tight Direction Networks (2002)
A concrete reconstruction problem arising in Computer Vision motivates our investigation of combinatorial variations on the problem of drawing a graph with given direction vectors associated to its...
Camera Position Reconstruction and Tight Direction Networks (2002)
A concrete reconstruction problem arising in Computer Vision motivates our investigation of combinatorial variations on the problem of drawing a graph with given direction vectors associated to its...
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...
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...
On the Number of Embeddings of Minimally Rigid Graphs (2002)
Ciprian Borcea, Ileana Streinu
Rigid frameworks in some Euclidian space are embedded graphs having a unique local realization (up to Euclidian motions) for the given edge lengths, although globally they may have several. We study...
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...
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...
Expansive Motions and the Polytope of Pointed Pseudo-Triangulations (2001)
Günter Rote, Francisco Santos, Ileana Streinu
We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on 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...
Hamiltonicity and colorings of arrangement graphs (2000)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (ane or projective) and pseudocircle (spherical)...
A Combinatorial Approach to Planar Non-colliding Robot Arm Motion Planning (2000)
We propose a combinatorial approach to plan noncolliding motions for a planar robot arm. The approach works even with certain types of movable polygonal obstacles and flexible polygonal fences. This...
On Reconfiguring Tree Linkages: Trees can Lock (2000)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. In this paper we propose a related question: whether a...
Open Problems from CCCG 2001 (2000)
Erik D. Demaine, Joseph O'Rourke, Ileana Streinu, John Iacono
USA. orourke@cs.smith.edu. Supported by NSF Distinguished Teaching Scholars award DUE-0123154. Figure 1: An example of a monotone matching. [Str94] Ileana Streinu. Positive and negative results on...
Hamiltonicity and Colorings of (2000)
Arrangement Graphs Stefan, Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (ane or projective) and pseudocircle (spherical)...
On Reconfiguring Tree Linkages: Trees can Lock (1999)
Biedl, Therese, Demaine, Erik, Demaine, Martin, Lazard, Sylvain, Lubiw, Anna, O'Rourke, Joseph, ...
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex....
Stretchability of Star-like Pseudo-Visibility Graphs (1999)
We present advances on the open problem of characterizing vertex-edge visibility graphs (ve-graphs), reduced by results of O'Rourke and Streinu to a stretchability question for pseudo-polygons....
Jürgen Bokowski, Susanne Mock, Ileana Streinu
We present an elementary proof of the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3. Keywords: oriented matroid, pseudoline arrangement, Folkman-Lawrence...
Non-Stretchable Pseudo-Visibility Graphs (1999)
We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The construction is based on the characterization of vertex-edge...
On Reconfiguring Tree Linkages: Trees can Lock (1998)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. This problem been raised independently by several...
Illumination by Floodlights (1998)
William Steiger, Ileana Streinu
We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle OE ß, n points p 1 ; \Delta...
Non-Stretchable Pseudo-Visibility Graphs (1996)
Ileana Streinu Dept, Ileana Streinu
We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The construction is based on the characterization of vertex-edge...
Non-Stretchable Pseudo-Visibility Graphs (1996)
We exhibit a family of graphs which can be realized as visibility graphs of pseudo-polygons, but not of straight-line polygons, thus providing a negative answer to conjectures of Abello and Kumar,...
We solve two open problems posed by Goodman and Pollack[GP84] about sets of signed circular permutations (clusters of stars) arising from generalized configurations of points: recognition and...
We solve two problems posed by Goodman and Pollack in [GP84]. Given a planar finite set of points fp 1 ; \Delta \Delta \Delta ; p n g, for every pair 1 i ! j n choose a direction for the unique line...
Visibility in Pseudo-Polygons and Vertex-Edge Pseudo-Visibility Graphs (1995)
Joseph O'Rourke, Ileana Streinu
We extend the notion of visibility graph to pseudo-polygons defined on generalized configurations of points (cf. Goodman and Pollack[4]). This abstracts the classic concept by removing the condition...
Some positive and negative results in computational geometry / (1994)
"Graduate Program in Computer Science."
A Pseudo-Algorithmic Separation of Lines From Pseudo-Lines (1994)
William Steiger, Ileana Streinu
this paper we give an algorithmic-type of separation for these two classes via the complexity of sorting the elements of S, the x-coordinates