Suneeta Ramaswami: Research

Suneeta Ramaswami

322 Business and Science Building
Department of Computer Science
Rutgers University
Camden, NJ 08102
Email: suneeta.ramaswami at rutgers.edu

Publications (Journals Conferences) Quadrilateral meshing code

Research support Research-related links Coauthors

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, and computer graphics.

Publications

Many of the following papers are copyrighted, which means they can be distributed only for noncommercial purposes, and at no charge. Most electronically available papers are in compressed postscript or in pdf form.

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.

Journals (in preparation):

T. Lemos, S. Ramaswami, and M. Siqueira. An Experimental Comparison of Algorithms for Converting Triangulations of Closed Surfaces into Quadrangulations, to be submitted.

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.
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, Springer-Verlag, 2003.
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. Longer version at http://cgm.cs.mcgill.ca/cccg98/proceedings/.
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.

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.

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.

Research-related Links

Some web pages with lots of information related to computational geometry and its applications:

Geometry in Action : a superb compendium of the applications of geometry in the real-world. Explore also the geometry junkyard, which defies description. These pages are maintained by Prof. David Eppstein at UC-Irvine.

The Center for Geometric Computing .

A nice collection of geometric animation on the web can be found on Godfried Toussaint's web page .

The computational geometry bibliography , a search tool to look up references to publications in computational geometry.

Research support

My research is currently supported by the following grant:

NSF CCF-1422004. Amount: $198,936 (2014-2017). Collaborative grant with CCF-1422012 and CCF-1422019. Total budget: $451,243.

Past support by

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), and
Rutgers University start-up funds (1997-1999).