Search
Close this search box.

Computational Geometry Lab

At the School of Computer ScienceTel-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.

Motion Planning via Manifold Samples

Sailing around...

Robotic Sailing 2011 – Training and Competition

Arrangements of Geodesic Arcs on the Sphere

Arrangements of Geodesic Arcs on the Sphere

Polyhedral Assembly Partitioning with Infinite Translations

Optimized Synthesis of Snapping Fixtures

cgal arrangements and their applications

Yair Oz - Webcreator

Contact

Skip to content