Diane L. Souvaine

Research interests: Computational geometry, design and analysis of algorithms, computational complexity.

Selected publications:

• "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. Postscript.

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