Personal tools
You are here: Home
« February 2023 »
Log in

Forgot your password?

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.

arrangement of arcs on the sphere split star cover
Arrangements on a Sphere Assembly Planning CGAL Arrangements and Their Applications
cyanovirin_motion thumbnail IMG_4950 [i].JPG
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 tiny logo (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 split star of david assembly - project icon, which we use to compute a large family of Voronoi diagramssplit star of david assembly - project icon, Boolean operations, and Minkowski sumssplit star of david assembly - project icon. All about this and more can be found in our book CGAL Arrangements and Their Applicationssplit star of david assembly - project icon.

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 star of david assembly - project icon. We also develop algorithms that plan motions under mixed objective functionssplit star of david assembly - project icon (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 star of david assembly - project icon with many degrees of freedom, using motion-planning techniques from robotics. We are also devising tools for dynamic maintenance of molecular structuressplit star of david assembly - project icon under conformational changes. Recently, we have participated in the World Robotic Sailing Championship (WRSC) 2011split star of david assembly - project icon, which was held in L├╝beck, Germany. See our project pagesplit star of david assembly - project icon 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 roundingsplit star of david assembly - project icon") or controlled perturbationsplit star of david assembly - project icon.

  • Site Maintenance:
Efi Fogel
Document Actions