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

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 Boolean operations, and Minkowski sumssplit . All about this and more can be found in our book CGAL Arrangements and Their Applicationssplit.

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 planningsplit. We also develop algorithms that plan motions under mixed objective functionssplit  (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 motionsplit with many degrees of freedom, using motion-planning techniques from robotics. We are also devising tools for dynamic maintenance of molecular structuressplit under conformational changes. Recently, we have participated in the World Robotic Sailing Championship (WRSC) 2011 which was held in Lübeck, Germany. 

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 roundingsplit) or controlled perturbationsplit.

For more information please visit: https://acg.cs.tau.ac.il/