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