The Taub Faculty of Computer Science Events and Talks

The Computational Geometry Algorithms Library, CGAL, is the largest software collection of algorithms and data structures in Computational Geometry available today. It started a little over a decade ago as a European research project with a small number of partners and has grown over the years to be a huge open source project. The arrangement package of CGAL, developed at Tel Aviv University, constructs, maintains, traverses, and answers queries on two-dimensional arrangements (subdivisions) of general curves. We will start with a bird's eye view of the overall project, and then briefly present the underlying design principles of the arrangement package. The talk will mostly focus on recent innovations and applications of the arrangement package, including the construction of: general 2D Voronoi diagrams, envelopes of surfaces in three-dimensional space, Boolean set operations for generalized (curved) polygons, and more.

The new components that we will review were developed by Efi Fogel, Michal Meyerovitch, Ophir Setter, Ron Wein, and Baruch Zukerman.