Research – Suneeta Ramaswami

Research Interests

Computational geometry and the design, analysis and implementation of algorithms for geometric problems that arise in varied applications such as mesh generation, robotics, computer graphics, and medical imaging. My current work is on geometric techniques for mesh generation with quadrilateral mesh elements of bounded aspect ratios, for three-dimensional surfaces, and adaptive meshing techniques. (The image on the right shows a quadrilateral surface mesh resulting from our work on mesh generation for three-dimensional surfaces, as does the background image on my home page.)

Journals:

S. Ramaswami and M. Siqueira. A Fast Algorithm for Computing Irreducible Triangulations of Closed Surfaces in E^d, Computational Geometry: Theory and Applications, 68, 2018, pp. 327-357.
F. Hurtado, E. Molina, S. Ramaswami, and V. Sacristan. Distributed Reconfiguration of 2D Lattice-based Modular Robotic Systems, Autonomous Robots, 38(4), 2015, pp. 383-413.
B. Atalay, S. Ramaswami, and D. Xu, Quadrilateral Meshes with Provable Angle Bounds, Engineering with Computers, 28(1), 2012, pp. 31-56.
G. Aloupis, S. Collette, M. Damian, E. Demaine, D. El-Khechen, R. Flatland, S. Langerman, J. O’Rourke, V. Pinciu, S. Ramaswami, V. Sacristan, and S. Wuhrer, Efficient Constant-Velocity Reconfiguration of Crystalline Robots, Robotica, 29(1), 2011, pp. 59-71.
M. Damian, R. Flatland, J. O’Rourke, and S. Ramaswami, Connecting Polygonizations via Stretches and Twangs, Theory of Computing Systems, 47(3), 2010, pp. 674-695.
G. Aloupis, S. Collette, M. Damian, E. Demaine, R. Flatland, S. Langerman, J. O’Rourke, S. Ramaswami, V. Sacristan, S. Wuhrer, Linear Reconfiguration of Cube-Style Modular Robots, Computational Geometry: Theory and Applications, 42, 2009, pp. 652-663.
J. Colannino, M. Damian, F. Hurtado, S. Langerman, H. Meijer, S. Ramaswami, D. Souvaine and G. Toussaint. Efficient Many-to-Many Point Matching in One Dimension. Graphs and Combinatorics, 23, 2007, pp. 169-178.
J. Colannino, M. Damian, F. Hurtado, J. Iacono, H. Meijer, S. Ramaswami, and G. Toussaint, An O(n log n)-Time Algorithm for the Restriction Scaffold Assignment Problem, Journal of Computational Biology, 13(4), 2006.
S. Ramaswami, M. Siqueira, T. Sundaram, J. Gallier, and J. Gee, “Constrained Quadrilateral Meshes of Bounded Size”, International Journal of Computational Geometry and Applications, 15(1), 2005, pp. 55-98. ( Invited paper in special issue devoted to selected papers from IMR 2003). The algorithm in this paper has been implemented by Marcelo Siqueira. Downloadable code can be found here.
O. Aichholzer, D. Bremner, E. D. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia, Games on Triangulations, Theoretical Computer Science (special issue on “Game Theory Meets Theoretical Computer Science”), 343(1-2), 2005, pp. 42-71.
D. Bremner, F. Hurtado, S. Ramaswami, and V. Sacristan, Small Strictly Convex Quadrilateral Meshes of Point Sets, Algorithmica, 38(2), 2003, pp. 317-339. ( Invited paper in special issue devoted to selected papers from ISAAC 2001)
K. Miller, S. Ramaswami, P. Rousseeuw, T. Sellarès, D. Souvaine, I. Streinu, and A. Struyf, Efficient computation of depth contours by methods of computational geometry, Statistics and Computing, 13(2), 2003, pp. 153-162.
F. Gomez, S. Ramaswami, and G. Toussaint, Computing General Position Views of Data in Three Dimensions, Journal of Visual Communication and Image Representation, 13(4), 2002, pp. 401-424.
P. Bose, S. Ramaswami, G. Toussaint, and A. Turki, Experimental Results on Quadrangulations of Sets of Fixed Points, Computer Aided Geometric Design, 19(7), 2002, pp. 533-552.
O. Aichholzer, C. Cortes, V. Dujmovic, E. Demaine, J. Erickson, H. Meijer, M. Overmars, B. Palop, S. Ramaswami, and G. Toussaint, Flipturning Polygons, Discrete and Computational Geometry, 28, 2002, pp. 231-253.
F. Gomez, F. Hurtado, S. Ramaswami, V. Sacristan, and G. Toussaint, Implicit Convex Polygons, Journal of Mathematical Modelling and Algorithms, Vol. 1, 2002, pp. 57-85.
P. Bose, F. Hurtado, H. Meijer, S. Ramaswami, D. Rappaport, V. Sacristan, T. Shermer and G. Toussaint, Computing Sections of Arrangements: 2D results, Journal of Mathematical Modelling and Algorithms, Vol. 1, 2002, pp. 3-16.
Sanguthevar Rajasekaran and Suneeta Ramaswami, Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane and Related Problems, Algorithmica, Vol. 33, 2002, pp. 436-460.
P. Berman, B. DasGupta, S. Muthukrishnan, and S. Ramaswami, Improved Approximation Algorithms for Rectangle Tiling and Packing, Journal of Algorithms, Vol. 41, 2001, pp. 443-470.
Mark de Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami and Gordon Wilfong, Computing Constrained Minimum-Width Annuli of Point Sets, Computer-Aided Design (special issue on Computational Geometry and Computer-Aided Design & Manufacturing), Elsevier Press, Vol. 30, No. 4, 1998, pp. 267-275.
Suneeta Ramaswami, Pedro Ramos and Godfried Toussaint, Converting Triangulations to Quadrangulations, Computational Geometry: Theory and Applications, Elsevier Press, Vol. 9, 1998, pp. 257-276.
Sanguthevar Rajasekaran and Suneeta Ramaswami, Optimal Mesh Algorithms for the Voronoi Diagram of Line Segments and Motion Planning in the Plane, Journal of Parallel and Distributed Computing, Vol. 26, 1995, pp. 99-115.

Book Chapter:

S. Ramaswami, “Parallel Randomized Techniques for Some Fundamental Geometric Problems“, In P. Pardalos and R. Rajasekaran, editors, Advances in Randomized Parallel Computation, pp. 133-158, Kluwer Academic Publishers, 1999.

Conferences:

[Undergraduate student paper] C. Gillespie, M. Moore, and C. Brown. Quadrilateral Mesh Generation with a Provably Good Aspect Ratio Bound (Student Research Competition paper), In Proceedings of SIGCSE’17, Seattle, WA, March 08-11, 2017.
T. Lemos, S. Ramaswami, and M. Siqueira. An Experimental Comparison of Algorithms for Converting Triangulations of Closed Surfaces into Quadrangulations (Research Note), In Proceedings of 24th International Meshing Roundtable, Austin, TX, Oct 12-14, 2015. (Longer version)
Thiago Lemos, Suneeta Ramaswami, and Marcelo Siqueira. A Fast Algorithm for Computing Irreducible Triangulations of Closed Surfaces in E^d and Its Application to the TriQuad Problem, in Abstracts of the 24th Fall Workshop on Computational Geometry, Storrs, CT, Oct 31-Nov 1, 2014.
Ferran Hurtado, Enrique Molina, Suneeta Ramaswami, and Vera Sacristan. Distributed universal reconfiguration of 2D lattice-based modular robots, in Abstracts of the 29th European Workshop on Computational Geometry, Braunschweig, Germany, March 17-20, 2013.
Greg Aloupis, Muriel Dulieu, John Iacono, Stefan Langerman, Ozgur Ozkan, Suneeta Ramaswami, and Stefanie Wuhrer. Order type invariant labeling and comparison of point sets, in Abstracts of the 28th European Workshop on Computational Geometry, Assisi, Italy, March 19-21, 2012.
S. Hine, F. B. Atalay, D. Xu, and S. Ramaswami, Quadrilateral Meshes with Bounded Minimum Angle. (Video and short paper), in Proceedings of the 25th Annual ACM Symposium on Computational Geometry (SoCG’09), June 2009, Aarhus, Denmark.
G. Aloupis, S. Collette, M. Damian, E. Demaine, D. El-Khechen, R. Flatland, S. Langerman, J. O’Rourke, V. Pinciu, S. Ramaswami, V. Sacristan, and S. Wuhrer, Realistic Reconfiguration of Crystalline (and Telecube) Robots, in Proceedings of the 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR), December 2008.
B. Atalay, S. Ramaswami, and D. Xu, Quadrilateral Meshes with Bounded Minimum Angle, Proceedings of the 17th International Meshing Roundtable (IMR), October 2008, pp. 73-91.
M. Damian, R. Flatland, J. O’Rourke, and S. Ramaswami, Connecting Polygonizations via Stretches and Twangs, Proceedings of the 25th International Symposium on the Theoretical Aspects of Computer Science (STACS), February 2008, pp. 217-228.
A two-page version also appears in the Abstracts of the 17th Fall Workshop on Computational and Combinatorial Geometry, November 2007.
G. Aloupis, S. Collette, M. Damian, E. Demaine, R. Flatland, S. Langerman, J. O’Rourke, S. Ramaswami, V. Sacristan, S. Wuhrer, Linear Reconfiguration of Cube-Style Modular Robots, Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), LNCS 4835, 2007, pp. 208-219.
M. Damian, R. Flatland, J. O’Rourke, and S. Ramaswami, A New Lower Bound on Guard Placement for Wireless Localization, in Abstracts of the 17th Fall Workshop on Computational and Combinatorial Geometry, November 2007.
M. Damian, E. D. Demaine, M. Demaine, V. Dujmovic, D. El-Khechen, R. Flatland, J. Iacono, S. Langerman, H. Meijer, S. Ramaswami, D. L. Souvaine, P. Taslakian, G. T. Toussaint, Curves in the Sand: Algorithmic Drawing, in Proceedings of the 18th Canadian Conference on Computational Geometry, August 2006, pp. 11-15.
S. Ramaswami, M. Siqueira, T. Sundaram, J. Gallier, and J. Gee, A New Algorithm for Generating Quadrilateral Meshes and Its Application to FE-Based Image Registration, in Proceedings of the 12th International Meshing Roundtable, Santa Fe, New Mexico, September, 2003.
M. Siqueira, T. Sundaram, S. Ramaswami, J. Gallier, and J. Gee, Quadrilateral Meshes for the Registration of Human Brain Images, in Abstracts of the DIMACS Workshop on Medical Applications in Computational Geometry, New Brunswick, NJ, April 2-4, 2003.
O. Aichholzer, D. Bremner, E. D. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia, Geometric Games on Triangulations, in Abstracts of the 19th European Workshop on Computational Geometry, Bonn, Germany, March 24-26, 2003, pp. 89-92.
O. Aichholzer, D. Bremner, E. D. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia, Playing with Triangulations, in Proc. Japan Conference on Discrete and Computational Geometry, Tokyo, Japan, December 2002. Also appears in Lecture Notes in Computer Science 2866, Springer-Verlag, 2003, pp. 22-37.
D. Bremner, F. Hurtado, S. Ramaswami, and V. Sacristan, Small Convex Quadrangulations of Point Sets, Proc. International Symposium on Algorithms and Computation (ISAAC), Christchurch, New Zealand. Lecture Notes in Computer Science 2223, Springer-Verlag, 2001, pp. 623-635.
V. Brumberg, S. Ramaswami, and D. Souvaine, Experimental Results on Upper Bounds for Vertex Pi-Lights, Abstracts of the 11th Fall Workshop on Computational Geometry, Brooklyn, NY, November 2001.
K. Miller, S. Ramaswami, P. J. Rousseeuw, T. Sellares, D. Souvaine, I. Streinu, and A. Struyf, Fast implementation of depth contours using topological sweep, Proc. 12th Annual SIAM Symp. Discrete Algorithms (SODA), Washington DC, January 2001, pp. 690-699.
P. Berman, B. DasGupta, S. Muthukrishnan, and S. Ramaswami, Improved approximation algorithms for rectangle tiling and packing, Proc. 12th Annual SIAM Symp. Discrete Algorithms (SODA), Washington DC, January 2001, pp. 427-436.
O. Aichholzer, C. Cortes, V. Dujmovic, E. Demaine, J. Erickson, H. Meijer, M. Overmars, B. Palop, S. Ramaswami, and G. Toussaint, Flipturning Polygons, Proc. Japan Conference on Discrete and Computational Geometry, November, 2000.
P. Bose, F. Hurtado, H. Meijer, S. Ramaswami, D. Rappaport, V. Sacristan, T. Shermer and G. Toussaint, Computing Sections of Arrangements: 2D results, Proc. Tenth Canadian Conference on Computational Geometry, Montréal, Canada, Aug 10-12, 1998, pp. 20-21.
S. Ramaswami, Parallel Randomized Techniques for Some Fundamental Geometric Problems: A Survey, Workshop on Randomized Parallel Computing, IPPS and SPDP’98 Joint Conference, Orlando, Florida. Lecture Notes in Computer Science 1388, Springer-Verlag, 1998. (invited paper)
F. Gomez, F. Hurtado, S. Ramaswami, V. Sacristan and G. Toussaint, Implicit Convex Polygons, Abstracts of the Fourteenth European Workshop on Computational Geometry, Barcelona, Spain, 1998, pp. 83-85.
M. de Berg, P. Bose, D. Bremner, S. Ramaswami and G. Wilfong, Computing Constrained Minimum-Width Annuli of Point Sets, Proc. Fifth Annual Workshop on Algorithms and Data Structures (WADS’97), Halifax, Canada. Lecture Notes in Computer Science 1272, Springer-Verlag, 1997, pp. 392-401.
F. Gomez, S. Ramaswami and G. Toussaint, On Removing Non-degeneracy Assumptions in Computational Geometry, Proc. Third Italian Conference on Algorithms and Complexity, Rome, Italy. Lecture Notes in Computer Science 1203, Springer-Verlag, 1997, pp. 52-63.
P. Bose, S. Ramaswami, G. Toussaint and A. Turki, Experimental Comparison of Quadrangulation Algorithms for Sets of Points, Abstracts of the Twelfth European Workshop on Computational Geometry, Münster, Germany, 1996, pp. 39-40.
S. Ramaswami, P. Ramos and G. Toussaint, Converting Triangulations to Quadrangulations, Proc. Seventh Canadian Conference on Computational Geometry, Quebec City, Quebec, 1995, pp. 297-302.
S. Rajasekaran and S. Ramaswami, Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane and Related Problems, Proc. Tenth Annual ACM Symposium on Computational Geometry, Stony Brook, New York, 1994, pp. 57-66.
S. Rajasekaran and S. Ramaswami, Optimal Mesh Algorithms for the Voronoi Diagram of Line Segments, Visibility Graphs and Motion Planning in the Plane, Proc. 30th Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, 1992, pp. 382-391.

Other Abstracts:

F. Gomez, S. Ramaswami, and G. Toussaint, “On Removing Degeneracies in Computational Geometry”, Abstracts of the 914th meeting of the American Mathematical Society, Lawrenceville, New Jersey, 1996. Also in Abstracts of the Cuba Conference on Algorithms, November, 2000.

Code for Quadrilateral Mesh Generation

Our algorithm for constrained quadrilateral mesh generation has been implemented. Downloadable code, called CQMesh, can be found here. The code was developed by Marcelo Siqueira, one of the co-authors of this work.

Here’s a video (a little over 6 minutes) of our quad-tree based meshing algorithm to construct quadrilateral meshes with bounded angles (this paper). Presented at SoCG ’09.

Code to construct convex quadrilateral meshes for simple polygonal regions, possibly with holes, is available here. This quad mesh generation code, called RMesh, implements an adaptation of our algorithm to convert triangulations to quadrangulations. This project was carried out by Ryan Bowman, a Computer Science undergraduate who graduated from Rutgers-Camden in 2004.

This material is based upon work supported by the National Science Foundation under grants CCR-0204293 and CCF-0830589.

Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

The following research funding support is gratefully acknowledged:

NSF CCF-1422004. Amount: $198,936 (2014-2017). Collaborative grant with CCF-1422012 and CCF-1422019. Total budget: $451,243.
NSF CCF-0830589. Amount: $228,026 (2008-2013).
NSF CCR-0204293. Amount: $134,789 (2002-2007).
Lindback Minority Junior Faculty Award. Amount: $15,000 (2003-2004).
a Rutgers University ISATC (Information Sciences and Technology Council) pilot project grant. Amount: $24,700 (2001-2002).
Research Council grants (1999-2000, 2000-2001),

Coauthors on my research papers:

Oswin Aichholzer, Greg Aloupis, Betul Atalay, Mark de Berg, Piotr Berman, Prosenjit Bose, David Bremner, Carmen Cortes, Justin Colannino, Sebastian Collette, Mirela Damian, Bhaskar DasGupta, Erik Demaine, Martin Demaine, Vida Dujmovic, Dania El-Khechen, Jeff Erickson, Robin Flatland, Jean Gallier, Jim Gee, Francisco Gomez, Ferran Hurtado, John Iacono, Evangelos Kranakis, Hannes Krasser, Stefan Langerman, Henk Meijer, Kim Miller, S.Muthukrishnan, Mark Overmars Joe O’Rourke, Belen Palop, Val Pinciu, Sanguthevar Rajasekaran, Pedro Ramos, David Rappaport, Peter Rousseeuw, Vera Sacristan, Toni Sellarès, Saurabh Sethia, Tom Shermer, Marcelo Siqueira, Diane Souvaine, Ileana Streinu, Anja Struyf, Tessa Sundaram, Perouz Taslakian, Godfried Toussaint, Alain Turki, Jorge Urrutia, Gordon Wilfong, Stephanie Wuhrer, Dianna Xu.