Diane L. Souvaine

Professor Department of Computer Science Tufts University 161 College Avenue Medford, MA 02155 USA Office: (617) 627-2486, Halligan 107A FAX: (617) 627-2227 Office Hours: Send email to make an appointment Email: dls (at) cs (dot) tufts (dot) edu

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.
• 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.
• 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.
• 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.
• COMP 263/MATH 263: Advanced Topics in Computational Geometry : F'99, F'00, F'03, S'07, S'09.

Educational Outreach Programs:
• Tufts University Institute on Problem Solving using Discrete Mathematics for Gr. 5-9 Teachers .

Selected publications: (click here for additional publications )

• ``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. Online version .

• ``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, 2012. Online version .

• ``Disjoint Compatible Geometric Matchings,'' with Mashhood Ishaque and Csaba D. Tóth. Proc. 27th Sympos. on Comput. Geom. (Paris, 2011), ACM Press, pp. 125-134. Discrete Comput. Geom., (2012), to appear. Online version .

• ``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 .

• ``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:

• Department of Computer Science
• School of Engineering
• Graduate Program in Computer Science
• Graduate and Professional Studies
• Directions to the Medford Campus (location of the Tufts School of Arts, Sciences and Engineering) Tufts Medford Map