Computational Geometry Seminar

Wednesday, March 7th, 2007, 16:10-18:00

Room 309
Schreiber Building

The Integration of Exact Arrangements with Effective Motion Planning

Ron Wein, Tel Aviv University

The field of Computational Geometry has greatly evolved over the last three decades, yielding a multitude of algorithms to solve real-life problems emerging from diverse application fields, such as Solid Modeling, Robotics and Geographical Information Systems. Yet implementing a geometric algorithm from a textbook is far from being a trivial task. Common assumptions in the design of algorithms are that all calculations can be carried out using exact arithmetic, and that the input objects are in general position. Unfortunately, these assumptions usually do not hold in practice.

The arrangement package of CGAL, the Computational Geometry Algorithms Library, is capable of constructing and maintaining planar subdivisions induced by a set of arbitrary planar curves, requiring only a small set of geometric predicates and constructions involving the curves. This package has gone through a major redesign process, which made it more flexible and extendible, while at the same time it led to major improvements in the package efficiency. The modular design of the arrangement package made it a convenient basis for the development of several peripheral CGAL packages, for computing Boolean operations on polygons, for constructing lower envelopes of 3D surfaces, etc. This robust software infrastructure has paved the way for providing more accurate solutions to motion-planning problems that arise in fields like Robotics and Computer-Aided Design. I will start the talk with an overview of the thesis results related to robust computation with arrangements and its applications.

I will then focus on a recent result regarding a fast approximation algorithm for offsetting a polygon, namely computing the Minkowski sum of a polygon and a disc. The offset-approximation algorithm employs only rational arithmetic, which significantly expedites its running times. At the same time, it provides guaranteed precision bounds. This algorithm is based on the infrastructure provided by the arrangement package, and it will be included in the forthcoming release of CGAL (Version 3.3). Using the offset infrastructure it is now possible to provide complete solutions to many practical problems in real time, as our experiments show.