Diane L. Souvaine
|
Professor of Computer Science
Adjunct Professor of Mathematics
Joyce Cummings Center 420, Medford/Somerville
Email: Diane (dot) Souvaine (at) tufts (dot) edu
Phone: 617-627-2486
Curriculum Vitae
|
Biography:
Dr. Diane L. Souvaine is a Professor of Computer Science and Adjunct Professor of Mathematics at Tufts University. She served as
Vice Provost for Research from 2012-2016 and then as Senior Advisor to the Provost at Tufts University from 2016-2018, drawing on institutional knowledge and experience to initiate, develop, and/or refine strategic projects that enhanced the mission and goals of Tufts. She previously served as Chair of the Department of Computer Science from 2002-2009.
Prior to Tufts, Dr. Souvaine was a member of the Rutgers University faculty for 12 years. During her tenure at Rutgers, she served in the Directorate of NSF’s Science and Technology Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a groundbreaking academic/industry collaboration of Princeton, Rutgers, Bell Labs and Bellcore. DIMACS is tasked with both the theoretical development of mathematics and computer science and their practical applications.
Dr. Souvaine received her Ph.D. in computer science from Princeton University from which she also received her M.S.E. in electrical engineering and computer science and M.A. in computer science. She earned an M.A.L.S. in mathematical sciences from Dartmouth College and graduated with distinction from Harvard University, earning an A.B.c.l. in English and American language and literature, with a second concentration in mathematics.
Her research contributions range from solving challenging problems in computational geometry to practical application across disciplines. In addition to her scientific and policy contributions, Dr. Souvaine is dedicated to increasing diversity and advancing women and underrepresented groups in mathematics, science, and engineering and works to enhance pre-college education in mathematics and computational thinking.
In 2008, President Bush appointed Dr. Souvaine to the National Science Board, a 24-member body that governs the National Science Foundation and advises the United States government about science policy. In 2014, President Obama reappointed her to the Board. She was elected Vice Chair on May 6, 2016 and Chair on May 3, 2018. In 2011 and in 2016, respectively, she was elected Fellow of the Association for Computing Machinery (ACM) and of the American Association for the Advancement of Science (AAAS). She serves on the Board of Trustees for the Computer History Museum and for TERC.
Research interests:
Computational geometry,
design and analysis of algorithms, and
computational complexity.
Teaching:
Tufts University courses taught:
- EN 47: Exploring Computer Science : S'00, S'01, X'01, F'20.
- COMP 11: Introduction to Computer Science : F'98, S'99.
- COMP 15: Introduction to Data Structures : F'00.
- COMP 150GT: Introduction to Graph Theory : F'11, S'19, F'19.
- COMP 160: Algorithms : F'98, F'99, F'01, F'02, F'03, F'04, F'07, F'08, F'09, F'10, F'12, S'18.
- COMP 163/MATH 163: Computational Geometry : S'99, S'00, S'01, S'02, S'03, S'04, S'05, F'06, S'08, S'11, F'18, S'20.
- COMP 263/MATH 263: Advanced Topics in Computational Geometry : F'99, F'00, F'03, S'07, S'09.
Selected publications: (click here for
additional publications )
- ``Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs,''
with Hugo A. Akitaya, R. Inkulu, Torrie L. Nichols, Csaba D. Tóth and Charles R. Winston.
In Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017).
PDF
- ``Diffuse reflection diameter in simple polygons,''
with Gill Barequet, Sarah M. Cannon, Eli Fox-Epstein, Benjamin Hescott, Csaba D. Tóth, and Andrew Winslow.
Discrete Applied Mathematics 210, 2016, 123-132.
PDF
- ``The Flip Diameter of Rectangulations and Convex Subdivisions,''
with Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Lóffler, Joshua Mermelstein, and Csaba D. Tóth.
Discrete Mathematics & Theoretical Computer Science (DMTCS) 18, 3, 2016, 4:1-17.
PDF
- ``Isoperimetric Enclosures,''
with Greg Aloupis, Luis Barba, Jean-Lou De Careful, and Stefan Langerman.
Graphs and Combinatorics, 31, 2015, 361-392.
PDF .
Proceedings of the Mexican Conference on Discrete Mathematics and Computational Geometry, 2013, 47-56.
PDF .
- ``Bichromatic compatible matchings,''
with Greg Aloupis, Luis Barba, and Stefan Langerman.
Computational Geometry, 48, 2015, 622-633.
PDF
- ``Disjoint Compatible Geometric Matchings,''
with Mashhood Ishaque and Csaba D. Tóth.
Discrete and Computational Geometry, 49, 2013, pp. 89-131.
PDF .
In Proc. 27th Sympos. on Comput. Geom. (Paris, 2011), ACM Press, pp. 125-134.
-
``Diffuse Reflections in Simple Polygons,''
with Gill Barequet, Sarah M. Cannon, Eli Fox-Epstein, Benjamin Hescott, Csaba D. Tóth, and Andrew Winslow.
Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium: Electronic Notes in Discrete Mathematics, 44, 2013, 345-350.
PDF
- ``Algorithms for Designing Pop-up Cards,''
with Abel, Z., Demaine, E. D., Demaine, M. L., Eisenstat, S., Lubiw, A., Winslow, A.
In Proceedings of 30th Symposium on Aspects of Computer Science, 2013.
PDF
- ``Hidden Mobile Guards in Simple Polygons,''
with Cannon, S. and Winslow, A.
In Proceedings of the 24th Canadian Conference on Computational Geometry, 2012.
PDF
- ``Convexifying Monotone Polygons While Maintaining Internal Visibility,''
with Aichholzer, O., Aloupis, G., Demaine, E., Demaine, M., Dujmovic, V., Hurtado, F., Lubiw, A., Rote, G., Schulz, A., Winslow, A.
Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011.
PDF
- ``Constrained Tri-Connected Planar Straight Line Graphs,''
with Ishaque, M., Tóth, C., Winslow, A.
In Proceedings of the 20th Fall Workshop on Computational Geometry, 2011.
Full version in Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics, 2013.
PDF
- ``Simultaneously Flippable Edges in Triangulations,''
with Csaba Tóth and Andrew Winslow.
Festschrift for Ferran Hurtado, Proceedings of XIV Spanish Conference on Computational Geometry, vol 7579 of LNCS, Springer, 2012.
PDF
- ``Bounded-Degree Polyhedronization of Point Sets,''
with Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint.
Computational Geometry: Theory and Applications, 46, 2, 2013, pp. 148-153.
PDF
- ``Convex Partitions with 2-Edge Connected Dual Graphs,''
with Marwan Al-Jubeh, Michael Hoffmann, Mashhood Ishaque, and Csaba D. Tóth.
Special issue of Journal of Combinatorial Optimization, 2010, to appear.
Online version .
- ``Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
,'' with Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, and Robert Schweller. Natural Computing, 7(3), 2008. Special issue of selected papers from the 13th International Meeting on DNA Computing, 2007, 347-370.
Online version .
- "A Tight Bound for Connecting Sites Across Barriers," with David Krumme, Eynat Rafalin, and Csaba Toth. Discrete and Computational Geometry, Springer New York, 2008. Online version . Conference version appeared in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG), Arizona, 2006, 439-448. Abstract
- "An Experimental Study of Old and New Depth Measures,'' with J. Hugg, E. Rafalin, and K. Seyboth. Workshop on Algorithm Engineering and Experiments (ALENEX06) ,
Springer-Verlag Lecture Notes in Computer Science, 2006, 51-64.
Pdf version
- ``An Intuitive Approach to Measuring Protein Surface Curvature,''
with Ryan G. Coleman, Michael A. Burr, and Alan C. Cheng.
Proteins: Structure, Function, and Bioinformatics , 61:4, 2005, pp. 1068-1074.
Abstract
- ``Hinged Dissection of Polypolyhedra,'' with Erik Demaine, Martin Demaine, and Jeff Lindy.
Lecture Notes in Computer Science: Proceedings of the Workshop on Algorithms and Data Structures 3608,
Springer-Verlag, 2005, 205-217.
Abstract
PDF
- ``A Vertex-Face Assignment for Plane Graphs,''
with Csaba Toth.
17th Annual Canadian Conference on Computational Geometry , Windsor, Ontario, August, 2005.
Invited submission for special issue of Computational Geometry: Theory and Applications. .
PDF .
- ``Planar Minimally Rigid Graphs and Pseudo-Triangulations,''
with R. Haas, D. Orden, G. Rote, F. Santos, B. Servatius, H. Servatius, I. Streinu and W. Whiteley,
Computational Geometry Theory and Applications, Volume 31, Issues 1-2, May 2005, Pages 31-61.
Prepublication version.
Preliminary version appeared in 19th ACM Symposium on Computational Geometry, 2003.
PDF.
- ``Topologically Sweeping the Complete Graph in Optimal Time and Space,''
with Eynat Rafalin. TUFTS-CS Technical Report 2003-05 , Tufts University, December, 2003. Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry , MIT, 2004, pages 1-2.
- ``Simplicial Depth: An Improved Definition, Analysis, and Efficiency for the Finite Sample Case,''
with Michael Burr and Eynat Rafalin. Proceedings of the 16th Canadian Conference on Computational Geometry , 2004.
Full version to appear in Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications , ed. by
Reginia Liu, AMS DIMACS Book Series, 2006.
Preliminary version
- ``Computational Geometry and Statistical Depth Measures,''
with E. Rafalin,
Theory and Applications of Recent Robust Methods, edited by
M. Hubert, G. Pison, A. Struyf, and S. Van Aelst, Series: Statistics for Industry and Technology, , Birkhauser, Basel, 2004, 283-296.
Postscript version
Pdf version
``Efficient Computation of Location Depth Contours by Methods of Combinatorial Geometry,''
with K. Miller, S. Ramaswami, P. Rousseeuw, T. Sellares, I. Streinu, A. Struyf.
Statistics and Computing, 2003, 153-162.
Pdf.
Postscript.
``Topological Sweep in Degenerate cases,''
with E. Rafalin, I. Streinu,
Algorithms Engineering and Experiments (ALENEX 2002) .
Springer-Verlag Lecture Notes in Computer Science 2409, 2002, 155-165.
Postscript version,
Pdf version
``Fast implementation of depth contours using topological sweep,''
with K. Miller, S. Ramaswami, P. Rousseeuw, T. Sellares, I. Streinu, A. Struyf.
Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms,
Washington, DC, January, 2001, Postscript.
``Constructing Piecewise Linear Homeomorphisms of Polygons with Holes,''
with Rephael Wenger and Mark Babikov.
Proceedings of the 9th Canadian Conference on Computational Geometry, 1997,
Postscript.
An earlier version appeared as DIMACS Technical Report 94-52
``Illumination of the Plane with Floodlights,''
with P. Bose, L. Guibas, A. Lubiw, M. Overmars, and J. Urrutia.
International Journal of Computational Geometry & Applications 7,
1997, 153--163.
Prepublication version.
``An Efficient Algorithm for Placing Guards in Polygons with
Holes,''
with I. Bjorling-Sachs.
Discrete and Computational Geometry, 13, January 1995, 77-109.
Prepublication version.
``Combinatorial Complexity of Signed Discs,''
with C.-K. Yap.
Computational Geometry: Theory and Applications, 5, 1995, 207-223.
Prepublication version.
``On Compatible Triangulations of Simple Polygons,''
with Boris Aronov and Raimund Seidel.
Computational Geometry: Theory and Applications, 1993, 27-35.
Prepublication version.
``Shortest Paths Help Solve Geometric Optimization Problems on Planar Regions,''
with E. A. Melissaratos.
SIAM J. Computing, 1992, 601-638.
Prepublication version.
``Computational geometry in a curved world,''
with D. P. Dobkin.
Algorithmica 5, 3, 1990, 421-457.
``Computing Median-of-Squares Regression Lines and
Guided Topological Sweep,''
with H. Edelsbrunner.
Journal of the American Statistical Association 85, 1990, 115-119.
``Computational Geometry -- A User's Guide,''
with D. P. Dobkin.
Chapter 2 of Advances in Robotics 1: Algorithmic and Geometric
Aspects of Robotics, J. T. Schwartz and C. K. Yap, eds., Lawrence Erlbaum Associates, 1987, 43-93.
Tufts University Information: