Robust and Efficient Software for Problems in 2.5-Dimensional Non-Linear Geometry

First, we achieve lower envelopes of quadrics using CGAL's Envelope_3 package. Second, we extend CGAL's Arrangement_2 package to support two-dimensional arrangements on a parametric reference surface. Two main examples are discussed: Arrangements induced by algebraic surfaces on an elliptic quadric and on a ring Dupin cyclide. Third, we decompose a set of quadrics or a set of algebraic surfaces into cells using a projection. Our goal is to achieve topological information for the surfaces, while preserving their geometric properties. We maintain a special two-dimensional arrangement; the lifting to the third dimension benefits from the recently presented bitstream Descartes method. The obtained cell decomposition supports a set of other geometric applications on surfaces.

Our implementations follow the geometric programming paradigm. That is, we split combinatorial tasks from geometric operations by generic programming techniques. It is also ensured that each geometric predicate returns the mathematically correct result, even if it internally exploits approximative methods to speed up the computation.

(The talk is 30min)