Ileana Streinu

Education

• Ph.D. in Computer Science, 1994, Rutgers University, New Brunswick, NJ.
• Doctorate in Mathematics/Computer Science, 1985(94), University of Bucharest, Romania.
• Diploma (B.S.) and Specialization (M.S.), Mathematics and Computer Science, University of Bucharest, Romania.

Research Interests

• Combinatorial and Computational Geometry
  • Geometric Algorithms (visibility, motion planning)
  • Rigidity Theory
  • Oriented Matroids and Pseudolines
  • Graph Theory
  • Robust Computation
  • Complexity of Geometric Algorithms
• with Applications in:
  • Computational Molecular Biology (Geometry of Protein Structure Determination, Protein Flexibility, Dynamics and Folding)
  • Computer Graphics
  • Robotics
  • Graph Drawing
  • Computational Statistics and Data Visualization
• Software development for:
  • Protein flexibility and motion simulation
  • Graph Drawing

Academic Honors

• The 2004 Moisil Prize of the Romanian Academy, in Theoretical Computer Science.
• DIMACS Fellowship, Rutgers University, 1992, 1993, 1994.
• Rutgers Graduate Scholars Award, 1990, 1991.
• Diploma with distinction (1st in class, GPA 10/10), University of Bucharest, Romania, 1977.

Experience

• 2003 --. Computer Science Department, Smith College, MA. Professor of Computer Science.
• 2005 --. Mathematics Department, Smith College, MA. Professor of Mathematics.
• 2002 -- . Computer Science Department, University of Massachusetts at Amherst. Adjunct Professor of Computer Science.
• 2000 - 2002. Computer Science Department, Smith College, MA. Chair of the Department.
• 2000 - 2003. Computer Science Department, Smith College, MA. Associate Professor of Computer Science.
• 1994 - 2000. Computer Science Department, Smith College, MA. Assistant Professor of Computer Science.
• 1989 - 1994. Computer Science Department, Rutgers University, NJ. Teaching Assistant and Instructor.
• 1981 - 1988. Research Associate, Department of Electrical Engineering, Polytechnic University of Bucharest, Romania.
• 1977 - 1988. National Institute for Management and Informatics, Bucharest, Romania. 1977-1980 programmer, 1981-1988 Research Associate ("Cercetator stiintific") Laboratory for Artificial Intelligence.

Visiting

• May-Oct. 2006. Gastprofessorin (Visiting Professor), Technische Universitaet Berlin, Germany.
• July 2005. Kyoto University, Japan.
• Spring 2003. Computer Science Department, Ecole Normale Superieure, Paris, France and LORIA at University of Nancy, France (sabbatical).
• Fall 2002. Computer Science Department, Stanford University, CA and DIMACS Center (Rutgers University)(sabbatical).
• Spring 2001. Rutgers University Center for Operations Research (RUTCOR), Rutgers University, NJ.
• Fall 1998. Department of Applied Mathematics, Universitat Politecnica de Catalunya, Barcelona, Spain (sabbatical).

Teaching Experience

Undergraduate courses (Smith College and Rutgers University):

• Computational Geometry
• Algorithms
• Seminar in Robotics
• Formal Languages and Automata
• Discrete Mathematics
• Data Structures (CS2) and Object-Oriented Programming
• Advanced Programming Techniques
• Operating Systems
• Databases
• Computer Literacy
• Introduction to Engineering: Designing Intelligent Robots (both as a college course and as a summer course for high-school students.)

Graduate courses and seminars:

• University of Massachusetts at Amherst:
  • Computational Geometry and Applications, Fall 2003, 2004, 2005.
  • Advanced Topics in Computational Geometry: Rigidity Theory and Applications, Fall 2005
• Rutgers University/RUTCOR: Lectures on Oriented Matroids, Spring 2001.

Other:

• Technische Universitaet Berlin: Pre-doc course in Rigidity Theory, June 2006.
• Stanford University: A crash course in rigidity theory, Jan. 2003.
• Universitat Politecnica de Barcelona, Spain: A crash course on oriented matroids, Fall 1998.
• Transylvania University, Brasov, Romania: Computational Geometry, Short course, Jan. 1997.
• Politecnica University and University of Bucharest, Bucharest, Romania: LISP, Programming Languages and Compilers, 1981-87.

Research Papers

1. Ruth Haas, Audrey Lee, Ileana Streinu and Louis Theran. Characterizing Sparse Graphs by Map Decompositions, accepted, to appear in Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC) , vol. 62, 2007
   
   
2. David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu and Shin-ichi Tanigawa. Enumerating Planar Minimally Rigid Graphs, in Proc. 12th Annual International Computing and Combinatorics Conference COCOON 2006, Taipei, Taiwan, 15-18 Aug. 2006
   
   
3. Audrey Lee, Ileana Streinu and Oliver Brock A Methodology for Efficiently Sampling the Conformation Space of Molecular Structures, in Physical Biology 2, SPECIAL FOCUS: Flexibility in biomolecules, Nov. 2005, S108-S115, doi:10.1088/1478-3975/2/4/S05
   
   
4. Audrey Lee, Ileana Streinu and Louis Theran. Finding and Maintaining Rigid Components, in Proc. Canadian Conference on Computational Geometry, Univ. of Windsor, Canada, 10-12 Aug. 2005.
   
   
5. Audrey Lee and Ileana Streinu. Pebble Game Algorithms and (k,l)-sparse Graphs, in European Conference on Combinatorics, Berlin, Germany, 4-9 Sept. 2005.
   
   
6. Jack Snoeyink and Ileana Streinu. Computing Rigid Components of Pseudo-Triangulations in Linear Time, in Proc. Canadian Conference on Computational Geometry, Univ. of Windsor, Canada, 10-12 Aug. 2005.
   
   
7. Ileana Streinu. Parallel Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs, in Patrick Healy, Nikola S. Nikolov (editors) Proc. Graph Drawing 2005 , Limerick, Ireland, 12-14 Sept. 2005. Springer LNCS, Volume 3843, pp. 421 - 433, 2006. DOI: 10.1007/11618058_38
   
   
8. Ileana Streinu. Pseudo Triangulations, Rigidity and Motion Planning, Discrete and Computational Geometry, vol. 34, no. 4, pp. 587-635, Dec. 2005.
   
   
9. Ciprian Borcea and Ileana Streinu. Singularities of Hinge Structures, in Effective Methods in Algebraic Geometry (MEGA), Porto Conte, Sardinia, May 2005.
   
   
10. Ileana Streinu and Walter Whiteley. Single-Vertex Origami and Spherical Expansive Motions, Proc. Japan Conf. Discrete and Comp. Geometry, Tokai University, Tokyo, Oct. 8-11 2004. Lecture Notes in Computer Science 3742, pp. 161-173, Springer 2005.
    
    
11. Greg Aloupis, Erik Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu and Godfried Toussaint. Unfolding Polyhedral Bands, Proc. 16th Canadian Conference on Computational Geometry (CCCG), Concordia University, Montreal, August 9-11, 2004. Full version Edge-unfolding nested polyhedral bands submitted to Computational Geometry Theory and Applications (invited).
    
    
12. Oswin Aichholzer, Günter Rote, Bettina Speckmann and Ileana Streinu. The Zigzag Path of a Pseudo-Triangulation, Proc. 8th International Workshop on Algorithms and Data Structures (WADS), Ottawa, Canada, pp. 377-388, Lecture Notes in Computer Science 2748, Springer Verlag, 2003.
    
    
13. Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Hermann Servatius, Diane Souvaine, Ileana Streinu and Walter Whiteley. Planar Minimally Rigid Graphs and Pseudo-triangulations, Proc. ACM Symp. Comp. Geometry (SoCG), San Diego, California, June 2003, pp. 154-163. Full journal version in Computational Geometry Theory and Applications, vol. 31, issue 1-2, pp. 31-61, May 2005.
    
    
14. Ileana Streinu and Sue Whitesides. Rectangle Visibility Graphs: Characterization, Construction and Compaction, in Proc. of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS) 2003 , Berlin, Germany, Feb. 28-March 1, 2003, H. Alt and M. Habib (eds.), Springer-Verlag LNCS Series, vol. 2607, pp. 26-37.
    
    
15. Jürgen Bokowski, Simon King, Susanne Mock and Ileana Streinu. A Topological Representation Theorem for Oriented Matroids, in Discrete and Computational Geometry, vol. 33, nr. 4, pp. 645-668, April 2005.
    
    
16. Greg Aloupis, Erik Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu and Godfried Toussaint. Flat state Connectivity of Linkages under Dihedral Motions, in Proc. 13th Annual Internat. Symp. Algorithms and Computation (ISAAC'02), Vancouver, Nov. 20--23, 2002, pp. 369-380.
    
    
17. Ileana Streinu and Elif Tosun. Camera Position Reconstruction and Tight Direction Networks, in Michael Goodrich and Stephen Kobourov (eds.), Proc. Graph Drawing'02, Aug. 26-28, 2002, Irvine, CA, Lecture Notes in Computer Science, Springer Verlag 2002.
    
    
18. Greg Aloupis, Erik Demaine, Henk Meijer,Joseph O'Rourke, Ileana Streinu and Godfried Toussaint. Flat state connectedness of Fixed Angle Chains: Special Acute Chains, Proc. 14th Canadian Conference on Computational Geometry, Univ. of Lethbridge, Alberta, Canada, Aug. 12-14, 2002.
    
    
19. Ciprian Borcea and Ileana Streinu. On the Number of Embeddings of Minimally Rigid Graphs, Proc. ACM Symp. Computational Geometry (SoCG), Barcelona, June 5-7, 2002. Journal version in Discrete and Computational Geometry, 31, Feb. 2004, pp. 287-303.
    
    
20. Ileana Streinu. Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons, in Saugata Basu and Laureano Gonzalez-Vega (eds.), Proceedings of the DIMACS Workshop on on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science,, 2003, pp. 181-206.
    
    
21. Günter Rote, Francisco Santos and Ileana Streinu. Expansive Motions and the Polytope of Pointed Pseudo-Triangulations, in Boris Aronov, Saugata Basu, Janos Pach and Micha Sharir (eds.), Discrete and Computational Geometry -- The Goodman-Pollack Festschrift, in the series: Algorithms and Combinatorics, Springer Verlag, Berlin, 2003, pp. 699-736.
    
    
22. Eynat Rafalin, Diane Souvaine and Ileana Streinu. Topological Sweep for Degenerate Point Sets, in D. Mount and C. Stein (eds), Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), San Francisco, Jan. 4-5, 2002, Lecture Notes in Computer Science, Springer Verlag, 2002.
    
    
23. Jürgen Bokowski, Susanne Mock and Ileana Streinu. The Folkman-Lawrence Topological Representation Theorem for Oriented Matroids - an elementary proof in rank 3, European Journal of Combinatorics, vol. 22, no. 5, pp. 601-615, July 2001.
    
    
24. Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Diane Souvaine, Toni Sellares, Ileana Streinu and Anja Struyf. Efficient computation of location depth contours by methods of computational geometry, Statistics and Computing, 13, pp. 153-162, 2003. A preliminary version Fast Implementation of Depth Contours using Topological Sweep, appeared in Proc. 11th SIAM-ACM Symp. on Discrete Algorithms (SODA) 2001, Washington, DC, Jan. 7-9, 2001, pp. 690-699.
    
    
25. Ileana Streinu. A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning, Proc. 41st ACM Annual Symposium on Foundations of Computer Science (FOCS), Redondo Beach, CA, Nov. 12-14, 2000, pp. 443-453.
    
    
26. Stefan Felsner, Ferran Hurtado, Marc Noy and Ileana Streinu. Hamiltonicity and Colorings of Arrangement Graphs, Proc. 11th ACM-SIAM Symposium on Discrete Algorithms SODA San Francisco, Jan. 9-11 2000, pp. 155-164. Journal version submitted to European Journal of Combinatorics , 2002.
    
    
27. Ileana Streinu. Non-Stretchable Pseudo-Visibility Graphs, Proc. 11th Canadian Conf. on Computational Geometry, Vancouver, August 1999, pp. 22-25. Journal version in Computational Geometry: Theory and Applications 31, pp. 195-206, 2005.
    
    
28. Ileana Streinu. Stretchability of Star-like Pseudo-Visibility Graphs, Proc. ACM Symposium on Computational Geometry, Miami Beach, June 1999, pp. 274-280.
    
    
29. Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint and Sue Whitesides. Locked and Unlocked Polygonal Chains in Three Dimensions, Discrete and Computational Geometry 26, pp. 269-281, 2001.
    Preliminary version appeared in Proc. 10th ACM-SIAM Symposyum on Discrete Algorithms (SODA), Jan. 1999, pp. S866-7.
    
    
30. Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint and Sue Whitesides. On Reconfiguring Tree Linkages: Trees can Lock, Discrete Applied Math. 117 (2002) pp. 293--297. Preliminary version appeared in 10th Canadian Conference on Computational Geometry, Montreal, Aug. 1998. abs:4-5.
    
    
31. William Steiger and Ileana Streinu. Illumination by Floodlights, Computational Geometry: Theory and Applications 10 (1998) 57-70. A preliminary version appeared as Positive and Negative Results on the Floodlight Problem, Proc. 6th Canadian Conference on Computational Geometry, Saskatoon, aug. 1994, pp. 87-96.
    
    
32. Joseph O'Rourke and Ileana Streinu. The vertex-edge visibility graph of a polygon, Computational Geometry: Theory and Applications 10 (1998), 105-120.
    
    
33. Joseph O'Rourke and Ileana Streinu. Pseudo-Visibility Vertex-Edge Visibility Graphs: Characterization and Recognition, Proc. ACM Symposium on Computational Geometry, Nice, France, June 1997, pp. 119-128.
    
    
34. Ileana Streinu. Clusters of Stars, Proc. ACM Symposium on Computational Geometry, Nice, France, June 1997, pp. 439-441.
    
    
35. Joseph O'Rourke, Tom Shermer and Ileana Streinu. Illuminating convex polygons with vertex floodlights, Proc. 7th Canadian Conference on Computational Geometry, Quebec City, aug. 1995, pp. 151-156.
    
    
36. William Steiger and Ileana Streinu. A pseudo-algorithmic separation of lines and pseudo-lines, Inf.Proc.Letters 53, pp. 295-299, 1995. A preliminary version appeared in Proc. 6th Canadian Conference on Computational Geometry, Saskatoon, aug. 1994, pp. 7-11.
    
    
37. Ileana Streinu. A Gödel-like Independent Sentence in a Theory of Pure LISP Programs, Recursive Function Theory Newsletter, no.33, June 1985.
    
    
38. Ileana Streinu. Grammar Directed Gödel Numberings, Internat. Jour. Computer Mathematics, vol.19, no.3-4, 1983, pp.223-237.
    
    
39. Ileana Streinu. Learning by Grammatical Inference, Revue Roumaine de Linguistique, tome XXVI, no.5, 1981, pp.435-454.
    
    
40. Ileana Streinu. Darboux Property for the Hierarchy of LL(k) languages, (in Romanian), in Studii si Cercetari Matematice, Bucharest, tome 30, no.5,1978, pp.579-593.
    
    
41. Ileana Streinu. LL(k) Languages are closed under union with finite ones, in Proc. 4th ICALP, Turku, Finland, Springer LNCS 53, 1977, pp.504-508.
    

Books and chapters

1. Ileana Streinu. Arrangements of geometric objects, in Kenneth H. Rosen (ed. in chief), Handbook of Discrete and Combinatorial Mathematics, CRC Press, 1999.
   
   
2. Ileana Streinu. LISP - the AI Programming Language (in Romanian), Scientific and Encyclopedic Publishing House, Bucharest, Romania, 1986, 262 pgs.

Invited Lectures at Special Events

1. Orienting the Rigidity Matroid, Workshop on Matroids and Oriented Matroids, CIRM Center at Luminy, France, 7-11 Oct. 2005.
2. Rigid components: geometric problems, combinatorial solutions, Invited 1-hour talk, Oberwolfach workshop on Discrete Geometry, Mathematical Research Institute, Oberwolfach, Germany, April 11-18, 2005.
3. Pebble Games for Graph Arboricity, invited talk at Discrete Math Day, 26 Feb. 2005, Wesleyan University, CT.
4. Folding Robot Arms, Proteins, Origamis: a Combinatorial Approach , invited plenary lecture at the Northeastern Section of the Mathematical Association of America meeting, Worcester Polytechnic Institute, MA, Nov. 20, 2004.
5. Folding Carpenter's Rules, Robot Arms, Proteins, invited talk at the Workshop on Automated Deduction in Geometry ADG 2004, Univ. of Florida at Gainesville, Sept. 15-18, 2004.
6. Pseudo-Triangulations and Rigidity: a Survey, invited talk at the Workshop on Rigidity and Applications, University of Calgary, Alberta, Canada, July 23-24, 2004.
7. Points in Motion, MSRI Workshop on Combinatorial and Discrete Geometry, Berkeley, CA, Nov. 17-21, 2003.
8. Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons, Invited speaker, DIMACS Workshop on Algorithmic Issues on Modelling Motion (Pankaj Agarwal and Leonidas Guibas, organizers). DIMACS/Rugers University, NJ. November 20, 2002.
9. Pseudo-triangulations and Rigidity: a survey and recent results, Invited plenary talk, Discrete, Combinatorial and Computational Geometry (R. Pollack, J.E. Goodman, C. Zhong, organizers), a satellite conference to the International Congress of Mathematicians, Beijing University, Beijing, August 13-17, 2002.
10. Opening Arms: a Combinatorial Approach, invited speaker, Special session on Robot Arm Manipulation: Geometric Challenges (under Science Innovation: Physical Science and Engineering), (Robert Connelly, organizer) at the AAAS ( American Association for the Advancement of Science ) meeting in Boston, Feb. 14-19, 2002.
11. Folding Carpenter's Rules, Robot Arms, Proteins: a Combinatorial Approach, Valley Discrete Math Day, University of Massachusetts at Amherst. Oct. 12, 2001.
12. Folding Carpenter Rulers, Robot Arms, Proteins: a Rigidity Theoretical Approach, featured speaker at the Stony Brook Workshop on Discrete and Computational Geometry, Oct. 28-29, 2000, SUNY at Stony Brook.
13. Moving Simple Polygons Rigidly, invited plenary lecture at the Annual Meeting of the New Jersey Chapter of Mathematical Association of America, Georgian Court College, NJ, April 8, 2000.
14. Pseudo-visibility Graphs in Pseudo-polygons (with J. O'Rourke), 26th Computational Geometry Day, Courant Institute of Mathematics, New York University, New York, Apr. 26, 1996.

Other Invited Talks, Seminar Talks and Presentations

1. A methodology for efficiently sampling the conformation space of molecular structures (with Audrey Lee), Flexweb Netseminar, Center for Biological Physics, Arizona State University, 17 Nov. 2005.
2. Flexibility of Cut and Subdivided Polyhedra, Dept. of Mathematics, Technical University Berlin, Germany, June 23, 2005.
3. Folding Carpenter's Rules, Robot Arms, Proteins and Origami, Computer Science Dept. Hamburg University, Germany, June 13, 2005.
4. Pebble Game algorithms and (k,l)-sparse graphs, Dept. of Mathematics, Hamburg University, Germany, June 7, 2005.
5. Folding Robot Arms, Origami, Proteins: what is the computational challenge?, St Anselm College, New Hampshire, April 29, 2005.
6. Pebble Game Algorithms for Graph Arboricity. Experimental Mathematics seminar (Doron Zeilberger, org.), Rutgers University, March 31, 2005.
7. Folding Carpenter’s Rules, Robot Arms, Proteins: a combinatorial approach. Invited lecture at Worcester Polytechnic, Discrete Mathematics seminar. March 2005.
8. Pebble Game Algorithms for Graph Arboricity. Discrete Mathematics seminar (Walter Whiteley, org.), York University, March 3, 2005.
9. Pebble Game Algorithms for Body-and-Bar Rigidity, IBM Research, T.J. Watson, Yorktown Heights, Jan. 6, 2005.
10. A Pebble Game Algorithm for Body-and-Bar Rigidity, CMS Winter 2004 Meeting, Montreal, Dec. 11-13, 2004
11. Folding Robot Arms, Proteins, Origamis, Computer Science Department, University of Texas at Dallas, April 2, 2004.
12. Folding Robot Arms, Proteins, Origamis, Discrete Mathematics Seminar, Computer Science Department, Yale University, March 22, 2004.
13. Pseudo-lines, pseudo-triangles and other pseudo's, Geometry Seminar, New York University, Courant Inst. Of Math., March 2004
14. Points in Motion, Department Seminar, Computer Science Department, Tufts University, Medford, MA, 29 Oct. 2003.
15. Singularities of Hinge Structures, AMS Regional Meeting 991, Special Session on Mathematical Molecular Biology, Oct. 24-25, 2003, Chapel Hill, NC.
16. Points in Motion, Theory Seminar, Computer Science Department, University of Massachusetts at Amherst, 21 Oct. 2003.
17. Orienting the Rigidity Matroid, Combinatorics, Geometry and Computation Graduierten Kolleg Seminar, Freie Universitaet Berlin, July 14, 2003.
18. Graph Realizations with partial Oriented Matroid constraints, RSME-AMS First Joint Meeting , special session 14 (Discrete and Computational Geometry), Seville, Spain, June 18-21, 2003.
19. Graph Realizations with partial Oriented Matroid constraints, Seminaire ALGO, LORIA, Nancy, June 12, 2003.
20. Graph Realizations with partial Oriented Matroid constraints, Seminaire GeCoAl, ENS Paris, May 2, 2003.
21. Folding and Unfolding Processes for Polygonal Linkages, with Applications to Structural Biology, NSF-DARPA CARGO Meeting, Santa Rosa, CA, May 12-14, 2003.
22. Oriented Matroids and Rigidity. Seminar talk, Seminaire Combinatoire algebrique et geometrique, at Universite Paris 6, Feb. 20, 2003.
23. Graph Realizations with Oriented Matroid Constraints. Symposium in honor of Prof. Jürgen Bokowski's 60th birthday, Darmstadt University, Darmstadt, Germany, Feb. 2-4, 2003.
24. A Crash Course in Rigidity, Computer Science Department, Stanford University, Jan.10 and 17, 2003.
25. Degrees of Freedom. Seminar talk, Graphics group, Computer Science Department, Stanford University, Dec. 12, 2002.
26. Towards a mathematical and algorithmic theory for the Protein Folding problem. Seminar talk, Department of Molecular Biology, University of Massachusetts at Amherst, Nov. 22, 2002.
27. Towards a mathematical and algorithmic theory for the Protein Folding problem. Seminar talk, Computational Biology group, Computer Science Department, Stanford University, Nov. 2, 2002.
28. A Combinatorial Approach to the Protein Folding Problem. DARPA strategic meeting on the Protein Folding Problem, Arlington, VA, Oct 28-29, 2002.
29. Towards a mathematical and algorithmic theory for the Protein Folding problem, Seminar talk, Department of Structural Biology, Stanford University, Oct. 18, 2002.
30. High degree curves generated by mechanisms, with applications in Rigidity, invited talk, AMS Regional Meeting, special session on Optimal Geometry of Curves and Surfaces (John Sullivan and Jason Cantarella, organizers), Madison, WI, Oct. 12-13, 2002.
31. On the number of embeddings of minimally rigid graphs, Geometry Seminar, Courant Institute of Mathematics, New York University, NY, Oct. 15, 2002.
32. Folding Carpenter's Rules, Robot Arms, Proteins: a Combinatorial Approach, Celera Genomics, Rockville, MD, Aug. 6, 2002.
33. Folding and Unfolding of Polygonal Linkages, NSF-DARPA CARGO Program kick-off meeting, Newport, RI, May 20-22, 2002.
34. On the Number of Embeddings of Minimally Rigid Graphs, Discrete Geometry and Graph Theory Seminar, Mathematics Department, Cornell University, April 26, 2002.
35. Folding Carpenter's Rules, Robot Arms, Proteins: a Combinatorial Approach, Mathematics Department Seminar. University of Georgia, Athens, GA, March 8, 2002.
36. Expansive Motions and the Polytope of Pointed Pseudo-triangulations, Geometry Seminar, Courant Institute, New York University, Nov. 20, 2001.
37. New and old results on Pseudo-triangulations, Theory/Operations Research Seminar, Carnegie-Mellon University, November 16, 2001.
38. Pseudo-Triangulations, Rigidity Theory and Efficiently Planning Non-Colliding Robot Arm Motions, Freie Universität Berlin, May 28, 2001.
39. Pseudo-Triangulations, Rigidity Theory and Efficiently Planning Non-Colliding Robot Arm Motions, Univ. of Massachusetts at Amherst Theory Seminar, May 1, 2001.
40. Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons, DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry, DIMACS/Rutgers University, March 12-16, 2001.
41. A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning, Rutgers Operations Research Center (RUTCOR) seminar, March 2, 2001.
42. A Rigidity Theoretic Approach to Planar Non-Colliding Planar Robot Arm Motion Planning, Geometry Seminar, Courant Institute of Mathematics, New York University, Feb. 6, 2001.
43. Rigidity of Pseudo-Triangulations, invited talk, AMS Regional Meeting, University of Toronto, Toronto, Canada, Sept. 23-24, 2000.
44. The Folkman-Lawrence Topological Representation Theorem for Oriented Matroids - an Elementary Proof in Rank 3, invited talk, Special Session on Oriented Matroids and Polyhedra, International Conference on Mathematical Programming, Atlanta, Aug. 7-11, 2000.
45. Polygonal Oriented Matroids, special session on Discrete and Combinatorial Geometry, American Math. Society Regional Meeting, Lowell, MA, April 1-2, 2000.
46. The Flexibility Oriented Matroid, 4th Geometry Festival, an International Workshop on Discrete Geometry and Rigidity, Eötvös University, Budapest, Hungary, Nov. 29 - Dec. 2, 1999.
47. Stretchability Questions for Pseudo-Visibility Graphs, Workshop on Oriented Matroids, Luminy, France, Oct. 4-8, 1999.
48. Pseudo-visibility graphs, Universidad de Madrid, Alcala de Henares, Spain, Jan. 14, 1999.
49. Pseudo-visibility in pseudo-polygons, Universidad de Cantabria, Santander, Spain, Dec. 10, 1998.
50. A Crash Course on Oriented Matroids, Departament of Applied Mathematics II, Universitat Politecnica de Catalunya, Barcelona, Nov. - Dec. 1998.
51. Pseudo-visibility graphs and oriented matroids, Technische Universität Darmstadt, Germany, Nov. 4, 1998.
52. The complexity of visibility graph recognition, Theory Seminar, Computer Science Department and Departament of Applied Mathematics II, Universitat Politecnica de Catalunya, Barcelona,Oct. 1998.
53. Pseudo vertex-edge visibility graphs, Courant Institute of Mathematics. Geometry Seminar, New York University, Mar. 22, 1996.
54. Pseudo vertex-edge visibility graphs, Geometry Seminar, McGill University, Montreal, Mar. 19, 1996.
55. Pseudo-visibility graphs and oriented matroids, 17th Combinatorics and Graph Theory Day (CONE), Smith College, Nov. 11, 1995.
56. A pseudo-algorithmic separation of lines and pseudo-lines, 14th Combinatorics and Graph Theory Day (CONE), Smith College, Sep. 24, 1994.

Conference Talks

1. Enumerating Planar Minimally Rigid Graphs, 15th Fall Workshop on Computational Geometry and Visualization, 18-19 Nov. 2005, Univ. of Pennsylvania.
2. Parallel Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs, Graph Drawing'05, Limerick, Ireland, Sept. 12-14, 2005.
3. Computing rigid components of pseudo-triangulation mechanisms in linear time, Canadian Conf. Comput. Geometry, Univ.of Windsor, Canada, Aug. 10-12, 2005.
4. Single-vertex origami and spherical expansive motions, Japan Conf. Discrete and Computational Geometry, Tokai University, Tokyo, Oct. 8-11, 2004.
5. On the Number of Embeddings of Minimally Rigid Graphs (with Ciprian Borcea), ACM Symp. Comput. Geometry (SoCG), Barcelona, June 5-7, 2002.
6. Expansive Motions and The Polytope of Pointed Pseudo-Triangulations , The 11th Annual Fall Workshop on Computational Geometry Brooklyn Polytechnic, Brooklyn, NY, Nov. 2-3, 2001.
7. The Spherical Carpenter's Rule Problem and Conical Origami Folds , The 11th Annual Fall Workshop on Computational Geometry Brooklyn Polytechnic, Brooklyn, NY, Nov. 2-3, 2001.
8. Fast Implementation of Depth Contours using Topological Sweep , 11th SIAM-ACM Symp. on Discrete Algorithms (SODA) 2001, Washington, DC, Jan. 7-9, 2001.
9. A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning , 41st ACM Annual Symposium on Foundations of Computer Science (FOCS), Redondo Beach, CA, Nov. 12-14, 2000.
10. Hamiltonicity and Colorings of Arrangement Graphs , 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, Jan 9-11, 2000.
11. Non-Stretchable Pseudo-Visibility Graphs , 11th Canadian Conf. on Computational Geometry, Vancouver, British Columbia, CA, Aug. 12-16, 2000.
12. Stretchability of Star-like Pseudo-Visibility Graphs , ACM Symposium on Computational Geometry, Miami Beach, June 1999, pp. 274-280.
13. Pseudo-Visibility Vertex-Edge Visibility Graphs: Characterization and Recognition , ACM Symposium on Computational Geometry, Nice, France, June 4-6, 1997.
14. Clusters of Stars , Fall Workshop on Computational Geometry, Johns Hopkins University, Oct. 11-12, 1996.
15. Positive and Negative Results on the Floodlight Problem , 6th Canadian Conference on Computational Geometry, Saskatoon, Canada, Aug. 1994.
16. A pseudo-algorithmic separation of lines and pseudo-lines , 6th Canadian Conference on Computational Geometry, Saskatoon, Canada, Aug. 1994.

Posters and Demos

1. Efficiently sampling the conformation space of molecular structures (with Audrey Lee and Oliver Brock), Workshop on Flexibility in Macromolecules, Tempe, Arizona, May 15-19, 2005.
2. Efficiently sampling the conformation space of molecular structures (with Audrey Lee and Oliver Brock), NSF-DARPA CARGO Meeting, Santa Fe, New Mexico, May 10-11, 2005.
3. Detecting rigid Components in Graphs (with Audrey Lee and Louis Theran), NSF-DARPA CARGO Meeting, Santa Fe, New Mexico, May 10-11, 2005.
4. Single Vertex Origami (with Audrey Lee), NSF-DARPA CARGO Meeting, Madison, Wisconsin, May 10-11, 2004.
5. Camera Position Reconstruction and Tight Direction Networks (with Elif Tosun), Graph Drawing'02, University of Irvine, CA, Aug. 26-28, 2002.
6. Clusters of Stars, ACM Symposium on Computational Geometry, Nice, France, June 4-6, 1997.

PhD Students

• Audrey Lee
• Louis Theran
• Naomi Fox

Posters with Undergraduate Students

1. (with Elif Tosun) Visualizing an algorithm for robot arm reconfiguration, CCSCNE Conference, Middlebury College, April 19-20, 2001. Won the Best student poster award.
2. (with Beenish Chaudry, Geetika Tewari and Elif Tosun) A research tool for Oriented Matroids in Java, CCSCNE Conference, Ramapo College, NJ, April 2000.
3. (with Lilla Zollei) Clusters of Stars, CCSCNE Conference, April 1998.
4. (with Ling Lin) A Java applet for Rectangle Visibility Graphs, CCSCNE Conference, April 1998.
5. (with Roxana Cocan) Knot visualization, CCSCNE Conference, April 1998.

Research Grants

1. NSF RUI grant CCF-0430990, Oriented Matroid and Rigidity Theory Techniques in Computational Geometry, $180,000$. Principal Investigator, 2004-2007.
2. NSF-DARPA CARGO grant, Folding and Unfolding Processes for Polygonal Linkages, with Applications in Biology, Principal Investigator, $650000, 2003-2006. With Leonidas Guibas, Michael Levitt and R. James Milgram.
3. NSF-DARPA CARGO incubation grant CCR-0138374, Folding and Unfolding Processes for Polygonal Linkages, with Applications in Robotics and Biology, Principal Investigator, $99961, 2002-2003. With Leonidas Guibas, Michael Levitt and R. James Milgram.
4. NSF RUI grant CCR-0105507, Oriented Matroid and Rigidity Theory Techniques for Pseudo-Triangulations, Visibility Graphs and other structures in Computational Geometry, $108000. 3 year research grant, 2001-2004.
5. RUI NSF grant CCR-0203224, Workshops on Topics in Computational Geometry, $15000, 2002-04. For organizing a series of workshops at Bellairs Research Institute of McGill University in Barbados, West Indies.
6. NSF grant CCR-0104370, Workshop on Pseudo-Triangulations, 2001. For organizing a workshop at Bellairs Research Institute of McGill University in Barbados, West Indies.
7. Topics in Computational Geometry, NSF Grant CCR-9731804, 1998-2001, $150,000 and Grant supplement, 2000, $10,000. With Joseph O'Rourke.
8. Picker Fellowship, Smith College, 1998
9. Visibility, 3d and other topics in Computational Geometry, NSF Grant 94-21670, 1995-1997, $150,000. With Joseph O'Rourke.

Professional Activities

• Program Committee:
  • SoCG 2007
  • PC Chair, 16th Fall Workshop on Computational Geometry, Smith College, Nov. 10-11 2006.
  • ALENEX 2006
  • 15th Annual Fall Workshop on Computational Geometry, UPenn, Nov. 18-19, 2005.
  • 14th Annual Fall Workshop on Computational Geometry, MIT, Nov. 19-20, 2004.
  • DIMACS Fall Workshop on Computational Geometry, DIMACS, Rutgers University, Nov. 14-15, 2002.
  • ACM Annual Symposium on Computational Geometry (SoCG), 2001.
• Workshop Organizer:
  • 16th Fall Workshop on Computational Geometry, Nov. 10-11 2006 and a Rigidity Theory Day, 12 Nov. 2006, at Smith College.
  • Special sessions at AMS Meeting
    • Geometry of Protein Modeling , Special Session at the American Math. Society Regional Meeting 997, Rider University, Lawrenceville, NJ, April 17-18, 2004. Co-organizer (with Jack Snoeyink).
    • Discrete and Computational Geometry, Special Session at the American Math. Society Regional Meeting 914, Rider University, Lawrenceville, NJ, Oct. 5-6, 1996. Co-organizer (with W. Steiger).
  • Workshops on Topics in Computational Geometry, Bellairs Research Institute of McGill Univ. in Barbados.
    • Workshop on Dynamics under Costraints , Jan. 13-20, 2006.
    • Workshop on NMR Geometry and NMR Structure Determination , Jan. 14-21, 2005.
    • Workshop on the Geometry of Modeling Proteins , Jan. 16-23, 2004.
    • Workshop on the Geometry of Protein Folding , Jan. 24-31, 2003.
    • Workshop on Rigidity Theory and Scene Analysis, Jan. 11-18, 2002.
    • Workshop on Pseudo-Triangulations, Jan. 26-Feb.2, 2001.
• NSF Panel Reviewer.
• Editorial work:
  • Member of Editorial Board, Discrete and Computational Geometry.
  • Member of Editorial Board, Contributions to Discrete Mathematics.
  • Guest editor, special issue of Computational Geometry, Theory and Applications devoted to papers from the Fall Workshop on Computational Geometry, Nov. 2000, Stony Brook.
• PhD Committee, External Examiner: Computer Science Department, Queens University, Ontario, Canada. March 1998 and Tufts University, Medford, MA, March 2005.
• Reviewed papers submitted to Discrete and Computational Geometry, Computational Geometry: Theory and Applications, ACM Symposium on Computational Geometry, Symp. Theory of Computing (STOC), Discrete Mathematics, International Journal of Computational Geometry and Applications, SIAM Journal of Computing, Transactions of the AMS, Symposium on Computational Geometry (SoCG), ALENEX.

Other Educational and Outreach

1. Research Problems on Visibility, one week of lectures at Reconnect '99, an NSF-funded program, DIMACS Center, Rutgers University, NJ, July 19-23, 1999.
2. Computational Geometry, short course at Transylvania University of Brasov, Romania, Jan. 6-10 1997. Funded from a European TEMPUS grant.
3. Supervised over 30 undergraduate student projects, summer REU and honors thesis, Smith College.
4. Designing Intelligent Robots: an Introduction to Engineering, Smith College Summer Science Program for high school girls, 1999, 2000, 2001. Featured on Nickelodeon (2001) and local news on Western Massachusetts TV and radio stations and local newspapers (1999).