Computational Geometry Lab
At the School of Computer Science, Tel-Aviv University.
Computational Geometry is a branch of Computer Science dedicated to solving geometric problems using effective algorithms and data structures. Computational geometry techniques are applicable in many domains including robotics amd automation, geographic information systems (GIS), service location problems and many other geometric optimization problems, Computer Aided Design and Manufacturing (CAD/CAM) systems, to name just a few.
Research Topics
We study a variety of aspects of computational geometry and its applications. For more details about each topic, click on example projects highlighted below.
Algorithms in robotics and automation
A major area of research in the lab is 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. 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 on-going study is efficient assembly planning and object reconfiguration (a.k.a. object rearrangement).
Construction and manipulation of arrangements
We have developed techniques for 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. On 2023 CGAL was given the Test of Time Award for 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.
