Ileana Streinu

Last updated
Ileana Streinu
Ileana Streinu in Limerick.jpg
Alma mater University of Bucharest
Rutgers University
Known forWork on kinematics, structural rigidity
Scientific career
Fields Computer Science, Mathematics
Institutions Smith College
Doctoral advisor Solomon Marcus
William L. Steiger

Ileana Streinu is a Romanian-American computer scientist and mathematician, the Charles N. Clark Professor of Computer Science and Mathematics at Smith College in Massachusetts. [1] She is known for her research in computational geometry, and in particular for her work on kinematics and structural rigidity.

Contents

Biography

Streinu did her undergraduate studies at the University of Bucharest in Romania. She earned two doctorates in 1994, one in mathematics and computer science from the University of Bucharest under the supervision of Solomon Marcus and one in computer science from Rutgers University under the supervision of William L. Steiger. [1] [2] She joined the Smith computer science department in 1994, was given a joint appointment in mathematics in 2005, and became the Charles N. Clark Professor in 2009. [1] She also holds an adjunct professorship in the computer science department at the University of Massachusetts Amherst. [3]

At Smith, Streinu is director of the Biomathematical Sciences Concentration [4] [5] and has been the co-PI on a million-dollar grant shared between four schools to support this activity. [6]

Awards and honors

In 2006, Streinu won the Grigore Moisil Award of the Romanian Academy for her work with Ciprian Borcea using complex algebraic geometry to show that every minimally rigid graph with fixed edge lengths has at most 4n different embeddings into the Euclidean plane, where n denotes the number of distinct vertices of the graph. [7] [8]

In 2010, Streinu won the David P. Robbins Prize of the American Mathematical Society for her combinatorial solution to the carpenter's rule problem. In this problem, one is given an arbitrary simple polygon with flexible vertices and rigid edges, and must show that it can be manipulated into a convex shape without ever introducing any self-crossings. Streinu's solution augments the input to form a pointed pseudotriangulation, removes one convex hull edge from this graph, and shows that this edge removal provides a single degree of freedom allowing the polygon to be made more convex one step at a time. [9] [10] [11]

In 2012 she became a fellow of the American Mathematical Society. [12]

Selected publications

Related Research Articles

<span class="mw-page-title-main">Three utilities problem</span> Mathematical puzzle of avoiding crossings

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.

The carpenter's rule problem is a discrete geometry problem, which can be stated in the following manner: Can a simple planar polygon be moved continuously to a position where all its vertices are in convex position, so that the edge lengths and simplicity are preserved along the way? A closely related problem is to show that any non-self-crossing polygonal chain can be straightened, again by a continuous transformation that preserves edge distances and avoids crossings.

<span class="mw-page-title-main">Pseudotriangle</span>

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

<span class="mw-page-title-main">Moser spindle</span> Undirected unit-distance graph requiring four colors

In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.

Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.

<span class="mw-page-title-main">Laman graph</span>

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. This characterization, however, had already been discovered in 1927 by Hilda Geiringer.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Structural rigidity</span> Combinatorial theory of mechanics and discrete geometry

In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.

<span class="mw-page-title-main">Matchstick graph</span> Graph with edges of length one, able to be drawn without crossings

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph and a plane graph. For this reason, matchstick graphs have also been called planar unit-distance graphs. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.

In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.

In geometric graph theory, and the theory of structural rigidity, a parallel redrawing of a graph drawing with straight edges in the Euclidean plane or higher-dimensional Euclidean space is another drawing of the same graph such that all edges of the second drawing are parallel to their corresponding edges in the first drawing. A parallel morph of a graph is a continuous family of drawings, all parallel redrawings of each other.

In computational geometry, the star unfolding of a convex polyhedron is a net obtained by cutting the polyhedron along geodesics through its faces. It has also been called the inward layout of the polyhedron, or the Alexandrov unfolding after Aleksandr Danilovich Aleksandrov, who first considered it.

A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.

Flattenability in some -dimensional normed vector space is a property of graphs which states that any embedding, or drawing, of the graph in some high dimension can be "flattened" down to live in -dimensions, such that the distances between pairs of points connected by edges are preserved. A graph is -flattenable if every distance constraint system (DCS) with as its constraint graph has a -dimensional framework. Flattenability was first called realizability, but the name was changed to avoid confusion with a graph having some DCS with a -dimensional framework.

Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

References

  1. 1 2 3 Curriculum vitae [ permanent dead link ], retrieved 2012-03-06.
  2. Ileana Streinu at the Mathematics Genealogy Project
  3. UMass Department of Computer Science Faculty Directory, retrieved 2012-03-06. Archived 2012-07-19 at the Wayback Machine
  4. Gibson, Elise (December 2011), Unlocking the Secrets of Life: Biology, math, technology converge in a hot new field, Alumnae Association of Smith College, archived from the original on 2016-03-03, retrieved 2012-03-06.
  5. Smith Biomathematical Sciences Concentration, retrieved 2012-03-06.
  6. Cummings, Kelsey (September 14, 2011), "National Science Foundation awards Smith $1 million biomathematics grant", The Sophian, archived from the original on September 10, 2012.
  7. People News, Smith College, January 2, 2007, archived from the original on July 30, 2012, retrieved 2012-03-06.
  8. Borcea & Streinu 2004.
  9. "David P. Robbins Prize", January 2010 Prizes and Awards (PDF), American Mathematical Society, January 14, 2010, pp. 37–38.
  10. Smith College Professor Recognized for Her Groundbreaking Mathematical Research, Smith College, January 14, 2010.
  11. Streinu 2005.
  12. List of Fellows of the American Mathematical Society, retrieved 2013-08-05.