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. Example are robotics (e.g., motion planning among obstacles), geographic information systems (GIS), (e.g. combining several layers of information in one map), service location problems (e.g., cellular-antenna placement), Computer Aided Design and Manufacturing (CAD/CAM) systems, and integrated circuit design/verification systems.
Research Topics
We study applied aspects of computational geometry. For more details about each topic, click on example projects highlighted below.
![]() |
![]() |
![]() |
Arrangements on a Sphere | Assembly Planning | CGAL Arrangements and Their Applications |
![]() |
![]() |
|
Molecular Motion Simulation | Motion Planning via Manifold Sampling |
Our Autonomous Sailboat |
Construction and manipulation of arrangements of geometric objects in practice. In particular we have been developing the (Computational Geometry Algorithms Library) 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
.
Algorithmic robotics and motion planning. Two major topics of current focus are (i) hybrid techniques that combine sampling-based methods for motion planning with exact arrangement-based techniques, and (ii) assembly planning. We also develop algorithms that plan motions under mixed objective functions
(e.g.,trade-off length of path and clearance from the obstacles). In addition, we address problems in structural bioinformatics, in particular the prediction of molecular motion
with many degrees of freedom, using motion-planning techniques from robotics. We are also devising tools for dynamic maintenance of molecular structures
under conformational changes. Recently, we have participated in the World Robotic Sailing Championship (WRSC) 2011
, which was held in Lübeck, Germany. See our project page
for more details.
Fixed-precision approximation of complex shapes. A major and largely open problem in geometric computing is how to consistently and efficiently represent complex shapes using limited-precision coordinates. We attack this problem by vertex rounding ("snap rounding") or controlled perturbation
.
- Site Maintenance:
Efi Fogel | ![]() |
![]() |