Tufts University Logo
Computational Geometry
Department of Computer Science
Home Research Topics People
Papers & Presentations
Courses Software Geometry Links
Reconfiguration of Polygonal Subdivisions via Recombination Hugo Akitaya, Andrei Gonczi, Diane Souvaine, Csaba D. Tóth and Thomas Weighill In Proceedings of the 31st European Symposium on Algorithms (ESA 2023).
Reconfiguration of Polygonal Subdivisions via Recombination Hugo Akitaya, Andrei Gonczi, Diane Souvaine, Csaba D. Tóth and Thomas Weighill The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022), 2nd Workshop on Combinatorial Reconfiguration.
Hop-Spanners for Geometric Intersection Graphs Jonathan Conroy and Csaba Tóth. In Proceedings of the 38th International Symposium on Computational Geometry (SOCG 2022).
Characterizing Universal Reconfigurability of Modular Pivoting Robots Hugo Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. In Proceedings of the 37th International Symposium on Computational Geometry (SOCG 2021).
Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection Jonathan Conroy, Christopher Thierauf, Parker Rule, Evan Krause,Hugo Akitaya, Andrei Gonczi, Matias Korman, and Matthias Scheutz. In Proceedings of the 37th IEEE International Conference on Robotics and Automation (ICRA 2021).
Reconfiguration of connected graph partitions Hugo Akitaya, Matthew D. Jones, Matias Korman, Christopher Meierfrankenfeld, Michael J. Munje, Diane L. Souvaine, Michael Thramann, and Csaba Tóth. To appear in Journal of Graph Theory.
Reconfiguration of connected graph partitions via recombination Hugo Akitaya, Matias Korman, Oliver Korten, Diane L. Souvaine, and Csaba Tóth. In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC 2021).
2048 without merging Hugo Akitaya, Erik D. Demaine, Jason S. Ku, Jayson Lynch, Mike Paterson, and Csaba Tóth. In Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG 2020).
Rock climber distance: Frogs versus dogs Hugo Akitaya, Leonie Ryvkin, and Csaba Tóth. In Proceedings of the 31st Canadian Conference on Computational Geometry (CCCG 2019).
Circumscribing polygons and polygonizations for disjoint line segments Hugo Akitaya, Matias Korman, Oliver Korten, Mikhail Rudoy, Diane Souvaine, and Csaba Tóth. In Proceedings of the 35th Symposium on Computational Geometry (SOCG 2019). Full paper appeared in Discrete & Computational Geometry (2020).
Maximum area axis-aligned square packings Hugo Akitaya, Matthew D. Jones, David Stalfa, and Csaba Tóth. In Proceedings of the 43rd Symposium on Mathematical Foundations of Computer Science (SODA 2018). Full paper appeared as "The reach of axis-aligned squares in the plane" in Discrete Optimization, Vol. 37 (2020).
Recognizing weak embeddings of graphs Hugo Akitaya, Radoslav Fulek, and Csaba Tóth. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (MFSC 2018). Full paper appeared in ACM Transactions on Algorithms, Vol. 15, Issue 4, pp. 1-27 (2019).
Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs Hugo A. Akitaya, R. Inkulu, Torrie L. Nichols, Diane L. Souvaine, Csaba D. Tóth, and Charles R. Winston. In Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017). Full paper appeared in Theoretical Computer Science, Vol. 789, pp. 50-63 (2019).
Freeze Tag Awakening in Euclidean Spaces Hugo Akitaya and Jingjin Yu. The 26th Fall Workshop on Computational Geometry.
Reconstruction of Weakly Simple Polygons from their Edges Hugo Akitaya and Csaba Tóth. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016). Full paper appeared in International Journal of Computational Geometry & Applications, Vol. 28, No. 02, pp. 161-180 (2018).
Simple Folding is Really Hard Hugo Akitaya, Erik D. Demaine, and Jason S. Ku. In Proceedings of 19th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2016).
Multi-Colored Spanning Graphs Hugo Akitaya, Maarten Löffler, and Csaba Tóth. In Proceedings of the 24th International Symposium on Graph Drawing & Network Visualization (GD 2016). Full paper appeared in Theoretical Computer Science, Vol. 833, pp. 11-25 (2020).
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).
Diffuse reflection diameter in simple polygons Gill Barequet, Sarah M. Cannon, Eli Fox-Epstein, Benjamin Hescott, Diane L. Souvaine, Csaba D. Tóth, and Andrew Winslow. Discrete Applied Mathematics 210, 2016, 123-132.
The Flip Diameter of Rectangulations and Convex Subdivisions Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane L. Souvaine, and Csaba D. Tóth. Discrete Mathematics & Theoretical Computer Science (DMTCS) 18, 3, 2016, 4:1-17.
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.
Isoperimetric Enclosures Greg Aloupis, Luis Barba, Jean-Lou De Careful, Stefan Langerman, and Diane L. Souvaine. Graphs and Combinatorics, 31, 2015, 361-392.
Bichromatic compatible matchings Greg Aloupis, Luis Barba, Stefan Langerman and Diane L. Souvaine. Computational Geometry, 48, 2015, 622-633.
Simple Folding is Strongly NP-Complete Hugo Akitaya, Erik D. Demaine, Jason S. Ku. In Proceedings of 24th Fall Workshop on Computational Geometry, 2014.
The Flip Diameter of Rectangulations and Convex Subdivisions Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane L. Souvaine, and Csaba D. Tóth. LATIN 2014, 478-489.
Disjoint Compatible Geometric Matchings Mashhood Ishaque, Diane L. Souvaine and Csaba D. Tóth. Discrete and Computational Geometry, 49, 2013, pp. 89-131.
Isoperimetric Enclosures Greg Aloupis, Luis Barba, Jean-Lou De Careful, Stefan Langerman, and Diane L. Souvaine. Proceedings of the Mexican Conference on Discrete Mathematics and Computational Geometry, 2013, 47-56.
Diffuse Reflections in Simple Polygons Gill Barequet, Sarah M. Cannon, Eli Fox-Epstein, Benjamin Hescott, Diane L. Souvaine, 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.
Bounded-Degree Polyhedronization of Point Sets Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schultz, Diane L. Souvaine, Godfried T. Toussaint, and Andrew Winslow. Computational Geometry: Theory and Applications, 46, 2, 2013, pp. 148-153.
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.