Tufts University Logo
Computational Geometry
Department of Computer Science
Home Research Topics Software People
Papers & Presentations
Courses Geometry Links
Trash Compaction Hugo Akitaya, Greg Aloupis, Maarten Löffler, and Anika Rounds. In Proceedings of The European Workshop on Computational Geometry (EuroCG 2016).
Recognizing Weakly Simple Polygons Hugo Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. Tóth. In Proceedings of 32nd International Symposium on Computational Geometry (SoCG 2016).
Box Pleating is Hard Hugo Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, and Ryuhei Uehara. In Proceedings of 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015).
Augmenting Planar Straight Line Graphs to 2-Edge-Connectivity Hugo Akitaya, Jonathan Castello, Yauheniya Lahoda, Anika Rounds and Csaba D. Tóth. In Proceedings of 25th Fall Workshop on Computational Geometry, 2015.
Simple Folding is Strongly NP-Complete Hugo Akitaya, Erik D. Demaine, Jason S. Ku. In Proceedings of 24th Fall Workshop on Computational Geometry, 2014.
Covering Folded Shapes Aichholzer, O., Aloupis, G., Demaine, E. D., Demaine, M. L., Fekete, S., Hoffmann, M., Lubiw, A., Snoeyink, J., Winslow, A. In Proceedings of 25th Canadian Conference on Computational Geometry, 2013.
Staged Self-Assembly and Polyomino Context-Free Grammars Winslow, A. In Proceedings of 19th International Conference on DNA Computing and Molecular Programming, 2013.
Diffuse Reflections in Simple Polygons Barequet, G., Cannon, S. M., Fox-Epstein, E., Hescott, B., Souvaine, D. L., Tóth, C., Winslow, A. In Proceedings of 7th Latin-American Algorithms, Graphs, and Optimization Symposium, 2013.
Two Hands are Better than One (up to constant factors): Self-Assembly in the 2HAM vs. aTAM Cannon, S., Demaine, E. D., Demaine, M. L., Eisenstat, S., Patitz, M. J., Schweller, R. T., Winslow, A. In Proceedings of 30th Symposium on Aspects of Computer Science, 2013.
Algorithms for Designing Pop-up Cards Abel, Z., Demaine, E. D., Demaine, M. L., Eisenstat, S., Lubiw, A., Souvaine, D. L., Winslow, A. In Proceedings of 30th Symposium on Aspects of Computer Science, 2013.
Hidden Mobile Guards in Simple Polygons Cannon, S., Souvaine, D., Winslow, A. In Proceedings of the 24th Canadian Conference on Computational Geometry, 2012.
Algorithms for Solving Rubik's Cubes Demaine, E. D., Demaine, M. L., Eisenstat, S., Lubiw, A., Winslow, A. In Proceedings of 19th European Symposium on Algorithms, 2011.
Convexifying Monotone Polygons While Maintaining Internal Visibility Aichholzer, O., Aloupis, G., Demaine, E., Demaine, M., Dujmovic, V., Hurtado, F., Lubiw, A., Rote, G., Schulz, A., Souvaine, D., Winslow, A. In Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011.
One-Dimensional Staged Self-Assembly Demaine, E., Eisenstat, S., Ishaque, M., WInslow, A. In Proceedings of the 17th International Conference on DNA Computing and Molecular Programming, 2011. Full version in Natural Computing, 2013.
Disjoint Compatible Geometric Matchings Ishaque, M., Souvaine, D., Tóth, C. In Proceedings of the 27th Symposium on Computational Geometry, 2011.
Simultaneously Flippable Edges in Triangulations Souvaine, D., Tóth, C., Winslow, A. In Proceedings of the XIV Spanish Meeting on Computational Geometry, 2011. Full version in Ferran Hurtado Festschrift, LNCS 7579, 2012.
Constrained Tri-Connected Planar Straight Line Graphs Ishaque, M., Souvaine, D., 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.
Bounded-Degree Polyhedronization of Point Sets Barequet, G., Benbernou, N., Charlton, D., Demaine, E., Demaine M., Ishaque, M., Lubiw, A., Schulz, A., Souvaine, D., Toussaint, G., Winslow, A. In Proceedings of the 22nd Canadian Conference on Computational Geometry, 2010. Full version in Computational Geometry: Theory and Applications, 2013.
Connecting Obstacles in Vertex-Disjoint Paths. Al-Jubeh, M., Barequet, G., Ishaque, M., Souvaine, D., and Tóth, C. In Proceedings of the 26th European Workshop on Computational Geometry, 2010.
Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs. Al-Jubeh, M., Ishaque, M., Rédei, K., Souvaine, D., and Tóth, C. In Proceedings of the 20th International Symposium on Algorithms and Computation, 2009, 902-912.
Convex Partitions with 2-Edge Connected Dual Graphs. Al-Jubeh, M., Hoffmann, M., Ishaque, M., Souvaine, D., and Tóth, C. In Proceedings of the 15th International Computing and Combinatorics Conference, 2009, 192-204. Abstract appeared in Proceedings of 18th Fall Workshop on Computational Geometry, 2008, 63-64. Full paper to appear in the special issue of Journal of Combinatorial Optimization.
Shooting Permanent Rays Among Disjoint Polygons in the Plane. Speckmann, B., Ishaque, M., and Tóth, C. In Proceedings of the 25th Annual ACM Symposium on Computational Geometry, 2009, 51-60.
Relative Convex Hulls in Semi-Dynamic Subdivisions. Ishaque, M., and Tóth, C. In Proceedings of the 16th Annual European Symposium on Algorithms, 2008, 780-792.
Restricted Triangular Range Searching. Benbernou, N., Ishaque, M., and Souvaine, D. In Proceedings of the 20th Canadian Conference on Computational Geometry, 2008, 15-18.
Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues. Demaine, E., Demaine, M., Fekete, S., Ishaque, M., Rafalin, E., Schweller, R., and Souvaine, D. In Proceedings of the 13th International Meeting on DNA Computing, 2007, . Full paper appeared in the special issue of Journal of Natural Computing, 2008, 347-370.
Efficient Many-to-Many Point Matching in One Dimension. Colannino, J., Damian, M., Hurtado, F., Langerman, S., Meijer, H., Ramaswami, S., Souvaine, D., and Toussaint, G. In Proceedings of the Kyoto International Conference on Computational Geometry and Graph Theory, 2007. Full paper to appear in the Akiyama-Chv'atal Festschrift, a special supplement to the journal Graphs and Combinatorics.
Deflating The Pentagon Erik Demaine, Martin Demaine, Diane Souvaine and Perouz Taslakian Proceedings of the 23rd European Workshop on Computational Geometry (EWCG'07) Graz (Austria), 2007.
Computing the Tool Path of an Externally Monotone Polygon in Linear Time Prosenjit Bose, David Bremner and Diane Souvaine Proceedings of the 18th Canadian Conference on Computational Geometry, 2006, 85-88.
Curves in the Sand: Algorithmic Drawing Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Dania El-Khechen, Robin Flatland, John Iacono, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane Souvaine, Perouz Taslakian and Godfried T. Toussaint Proceedings of the 18th Canadian Conference on Computational Geometry, 2006, 11-14.
A Tight Bound for Connecting Sites Across Barriers. Krumme, D. W., Rafalin, E., Souvaine, D. L., and Tóth, C. D. In SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry (New York, NY, USA, 2006), ACM Press, pp. 439-448.
Depth explorer - a software tool for the analysis of depth measures. Hugg, J., Rafalin, E., and Souvaine, D. At the International Conference on Robust Statistics (2006).
Medians in multimodal data and the new proximity data depth. Rafalin, E., Seyboth, K., and Souvaine, D. In International Conference on Robust Statistics (2006).
An Experimental Study of Old and New Depth Measures. Hugg, J., Rafalin, E., Seyboth, K., and Souvaine, D. In Workshop on Algorithm Engineering and Experiments (ALENEX06) (2006), Springer-Verlag Lecture Notes in Computer Science, pp. 51-64.
Simplicial Depth: An Improved Definition, Analysis, and Efficiency for the Finite Sample Case. Burr, M., Rafalin, E., and Souvaine, D. In Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications, ed. by Reginia Liu, Robert Serfling, Diane Souvaine, and Yehuda Vardi, AMS/DIMACS Book Series, 2006, pp. 195-209. Preliminary versions appeared in the Proceedings of the 16th Canadian Conference on Computational Geometry, 2004, 136-139, and as DIMACS Technical Report 2003-28 and TUFTS-CS Technical Report 2003-01 in September 2003.
A Vertex-Face Assignment for Plane Graphs. Toth, C., and Souvaine, D. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05) Windsor, Ontario, August, 2005, pp. 138-141. Full paper invited to special issue of Computational Geometry: Theory and Applications.
Path Length in Proximity Graphs as a Data Depth Measure. Rafalin, E., Seyboth, K., and Souvaine, D. Tufts CS Technical Report 2005-5, Tufts University, Nov. 2005. Abstract appeared in Proceedings of the 15th Annual Fall Workshop on Computational Geometry, UPenn, 2005, pages 11-12.
An Intuitive Approach to Measuring Protein Surface Curvature. Coleman, R. G., Burr, M. A., Souvaine, D. L., and Cheng, A. C. In Proteins: Structure, Function, and Bioinformatics, 61:4, 2005, pp. 1068-1074.
Hinged Dissection of Polypolyhedra. Demaine, E. D., Demaine, M. L., Lindy, J. F., and Souvaine, D. L. In Lecture Notes in Computer Science: Proceedings of the Workshop on Algorithms and Data Structures, vol. 3608. Springer Berlin / Heidelberg, 2005, pp. 205-217. Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry, MIT, 2004, pages 16-17.
Computational Geometry and Statistical Depth Measures. Rafalin, E., and Souvaine, D. In Theory and Applications of Recent Robust Methods, ed. by Reginia Liu, Robert Serfling, Diane Souvaine, and Yehuda Vardi, Statistics for Industry and Technology Series, Birkhauser, Basel, 2004, pp. 283-296.
Transformations and Algorithms for Least Sum of Squares Hypersphere Fitting. Burr, M., Cheng, A., Coleman, R., and Souvaine, D. In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04) (2004), pp. 104-107.
Theory and Applications of Recent Robust Methods. Souvaine, D., and Rafalin, E. Birkhauser, Basel, 2004, ch. Computational Geometry and Statistical Depth Measures, pp. 283-296.
Topologically Sweeping the Complete Graph in Optimal Time and Space. Rafalin, E., and Souvaine, D. Tufts CS Technical Report 2003-05, Tufts University, Dec. 2003. Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry, MIT, 2004, pages 1-2.
Dynamic Update of Half-space Depth Contours. Burr, M., Rafalin, E., and Souvaine, D. Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry, MIT, 2004, pages 3-4.
Efficient Computation of Location Depth Contours by Methods of Computational Geometry. Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, J. Antoni Sellares, Diane Souvaine, Ileana Streinu, and Anja Struyf. Statistics and Computing, pages 153-162, 2003.
Planar Minimally Rigid Graphs and Pseudo-Triangulations Haas, R., Orden, D., Rote, G., Santos, F., Servatius, B., Servatius, H., Souvaine, D., Streinu, I., and Whiteley, W. In SCG '03: Proceedings of the nineteenth annual ACM Symposium on Computational Geometry (New York, NY, USA, 2003), ACM Press, pp. 154-163. One of eight papers from the conference invited and printed in special issue of Computational Geometry: Theory and Applications, Volume 31, Issues 1-2 , May 2005, Pages 31-61.
Topological Sweep in Degenerate Cases. Rafalin, E., Souvaine, D., and Streinu, I. In Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX) (Berlin, 2002), vol. 2409 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 577-588.
Experimental Results on Upper Bounds for Vertex P-Lights. Brumberg, V., Ramaswami, S., and Souvaine, D. L. In Proc. of the 11 Annual Fall Workshop on Computational Geometry, New York, Nov., 2001.
Fast Implementation of Depth Contours Using Topological Sweep. Miller, K., Ramaswami, S., Rousseeuw, P., Sellares, T., Souvaine, D. L., Streinu, I., and Struyf, A. In Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms (2001), pp. 690-699.
Efficient Radio Wave Front Propagation for Wireless Radio Signal Prediction. Perkins, G., and Souvaine, D. DIMACS Technical Report 99-27, May 1999.
Constructing Piecewise Linear Homeomorphisms of Polygons with Holes Babikov, M., Souvaine, D., and Wenger, R. In Proceedings of the 9th Canadian Conference on Computational Geometry, 1997, 6-10.
Illumination of the Plane with Floodlights Bose, P., Guibas, L. J., Lubiw, A., Overmars, M. H., Souvaine, D. L., and Urrutia, J. International Journal of Computational Geometry and Applications 7, 1/2 (1997), 153-163. Preliminary version appeared in Proceedings of the Fifth Canadian Conference on Computational Geometry}, University of Waterloo, 1993, 399-404.
Testing Simple Polygons Arkin, E., Belleville, P., Mitchell, J., Mount, D., Romanik, K., and Souvaine, D. CGTA: Computational Geometry: Theory and Applications 8, 1997, pp. 97-114.Preliminary version appeared in Proceedings of the Fifth Canadian Conference on Computational Geometry, University of Waterloo, 1993, pp. 387-392.
An Efficient Algorithm for Placing Guards in Polygons with Holes Bjorling-Sachs, I., and Souvaine, D. Discrete and Computational Geometry, 13, 1995, pp. 77-109. A preliminary version of this paper appeared as "A Tight Bound for Guarding Polygons with Holes",Rutgers University Technical Report LCSR-TR-165, May, 1991. An abstract appeared in Final Report of the MSI Stony Brook Workshop on Computational Geometry}, October , 1991, 17.
Combinatorial Complexity of Signed Discs Yap, C.-K., and Souvaine, D. CGTA: Computational Geometry: Theory and Applications, 5, 1995, pp. 207-223. Conference version appeared in Lecture Notes in Computer Science: Proceedings of the Workshop on Algorithms and Data Structures 709, Springer-Verlag, 1993, 577-588. A preliminary version appeared as DIMACS Technical Report 92-54, December 1992.
Localizing an Object with Finger Probes Freimer, R., Khuller, S., Mitchell, J., Piatko, C., Romanik, K., and Souvaine, D. In Proceedings of Vision Geometry III, SPIE - The International Society for Optical Engineers, November 1994, pp. 272-283.
Clamping a Polygon Van Wyk, C. J., and Souvaine, D. In The Visual Computer, 10, Special issue on computational geometry, 1994, pp. 484-494. A preliminary version of this paper appeared as Rutgers University Technical Report LCSR-TR-98, Mar. 1989. Abstract appears in Abstracts of the First Canadian Conf. on Computational Geometry, McGill University, August, 1989.
On Compatible Triangulations of Simple Polygons Aronov, Seidel, and Souvaine, D. CGTA: Computational Geometry: Theory and Applications 3 (1993).
The Contour Problem for Restricted-Orientation Polygons Bjorling-Sachs, I., and Souvaine, D. Invited paper in Proceedings of the IEEE 80, 9, 1992, pp. 1449-1470. Abstract appears in Abstracts of the First Canadian Conference on Computational Geometry}, McGill University, August, 1989.
Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions. Melissaratos, E. A., and Souvaine, D. L. SIAM J. Computing 21, 4 (1992), 601-638.
Tight Bounds for Edge Guards in Monotone Polygons and Rectilinear Monotone Polygons. Bjorling-Sachs, I., and Souvaine, D. In Proceedings of the Fourth Canadian Conference on Computational Geometry, Memorial University of Newfoundland, August, 1992, pp. 93-98. Complete reports on this work appeared: "A Tight Bound for Edge Guards in Monotone Polygons," DIMACS Technical Report 92-52}, Nov., 1992; "A Tight Bound for Edge Guards in Rectilinear Monotone Polygons,"DIMACS Technical Report 93-12, Feb. 1993.
Coping with Inconsistencies: A New Approach to Produce Quality Triangulations of Polygonal Domains with Holes. Melissaratos, E. A., and Souvaine, D. L. In SCG '92: Proceedings of the eighth annual symposium on Computational geometry (New York, NY, USA, 1992), ACM Press, pp. 202-211. Preliminary version appeared as Rutgers University Technical Report LCSR-TR-163, April, 1991.
Detecting the Intersection of Convex Objects in the Plane. Dobkin, D. P., and Souvaine, D. In Computer Aided Geometric Design 8, 1991, pp. 181-199.
Illuminating Squares on a Transversal. Everett, H., Lyons, K., Reed, B., and Souvaine, D. In Proceedings of the Third Canadian Conference on Computational Geometry, Simon Fraser University, Aug. 1991, pp. 118-121.
The Aquarium Keeper's Problem. Czyzowicz, J., Egyed, P., Everett, H., Rappaport, D., Shermer, T., Souvaine, D., Toussaint, G., and Urrutia, J. In SODA '91: Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA, 1991), Society for Industrial and Applied Mathematics, pp. 459-464.
Computational Geometry in a Curved World. Dobkin, D. P., and Souvaine, D. L. Algorithmica 5, 1 (March 1990), 421-457.
How Hard Can It Be to Draw a Pie Chart? Van Wyk., C. J., and Souvaine, D. L. Mathematics Magazine, 63, 1990, pp. 165-172.
Shortest Paths, Visibility, and Optimization Problems in Planar Curvilinear Objects. Melissaratos, E. A., and Souvaine, D. L. In Proceedings of the Second Canadian Conference on Computational Geometry, University of Ottawa, 1990, pp. 337-342.
Computing Least Median of Squares Regression Lines and Guided Topological Sweep. Edelsbrunner, H., and Souvaine, D. L. Journal of the American Statistical Association 85, 409 (March 1990), 115-119.
Separating Bi-Chromatic Points by Parallel Lines. Asano, T., Hershberger, J., Pach, J., Sontag, E., Souvaine, D., and Suri, S. In Proceedings of the Second Canadian Conference Computational Geometry, University of Ottawa, 1990, pp. 46-49.
On Solving Geometric Optimization Problems Using Shortest Paths. Melissaratos, E. A., and Souvaine, D. L. In SCG '90: Proceedings of the sixth annual symposium on Computational geometry (New York, NY, USA, 1990), ACM Press, pp. 350-359.
Decomposition and Intersection of Simple Splinegons Dobkin, D. P., Van Wyk., C. J., and Souvaine, D. L. In Algorithmica 3, 4, 1988, pp. 473-486.
Efficient time and space algorithms for least median of squares regression Dobkin, D. P., Steele, J. M., and Souvaine, D. L. In Journal of the American Statistical Association 82, 1987, pp. 794-801.
Computational Geometry -- A User's Guide Dobkin, D. P., and Souvaine, D. L. Chapter 2 of Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, ed. by J. T. Schwartz and C. K. Yap., Lawrence Erlbaum Associates, 1987, pp. 43-93.