Research Topics

We study a variety of aspects of computational geometry and its applications. For more details about each topic, click on an example project highlighted below.

Algorithms in robotics and automation

A major area of research in the lab is the development of algorithms in robotics and automation. We have devised fast deterministic algorithms for motion planning for fleets of hundreds of simply-shaped robots, as well as sampling-based algorithms for several robot arms moving in complex and tight three-dimensional workspaces with high degrees of freedom configuration spaces, which led to the 2025 Deutsch award bestowal. We have also developed algorithms that plan motions under mixed objective functions (e.g., trade-off length of path and clearance from the obstacles), and we continue our study of optimal motion planning, which is vastly open even for a small number of simple robots. Another ongoing study is efficient assembly planning and object reconfiguration (a.k.a. object rearrangement).

Construction and manipulation of arrangements

We have developed techniques for the construction and manipulation in practice of fundamental structures in computational geometry: arrangements of geometric objects. In particular, we have been developing the CGAL (Computational Geometry Algorithms Library) 2D arrangement package and several central structures in two- and three-dimensional space that build on arrangements. These include envelopes of surfaces, which we use to compute a large family of Voronoi diagrams, Boolean operations, and Minkowski sums. All about this and more can be found in our book CGAL Arrangements and Their Applications. In 2023, CGAL was given the Test of Time Award for its impact on the computational geometry community over the years. Previously, we devised methods for fixed-precision approximation of complex shapes. A major problem in geometric computing is how to consistently and efficiently represent complex shapes using limited-precision coordinates. We attacked this problem by vertex rounding (“snap rounding”) or controlled perturbation. We used motion-planning techniques from robotics to address problems in structural bioinformatics. In 2011, we participated in the World Robotic Sailing Championship (WRSC), which was held in Lübeck, Germany.