Using arrangements of algebraic curves (provided by CGAL) we compute the exact topology of real algebraic surfaces of arbitrary degree \(D\). Our projection approach is similar to Collins’ cylindrical algebraic decomposition (cad). In comparison, we construct a special planar arrangement instead of a full cad in the projection plane. This way we reduce the number of output cells for a single surface to \(O(D^5)\). Furthermore, our approach applies numerical and combinatorial methods to minimize costly symbolic computations. The algorithm handles all sorts of degeneracies without transforming the surface into a generic position. Our experiments show good performance for many well known examples from algebraic geometry. Additionally, our analysis provides geometric information as it supports the computation of arbitrary precise samples of the input, including critical points.
The implementation is part of an experimental CGAL package and thus follows the geometric computing paradigm (generic programming in C++ plus exact geometric predicates and constructions). This way we split combinatorial data structures and algorithms from actual geometric operations. While the former set is implemented generically, the latter set is surface-specific. This allows to come up with models for different surfaces. For example, we distinguish implementations for quadrics (degree at most 2) and surfaces of any degree. As, in general, robust implementations on these surfaces are lacking these days, we consider our contribution to be an important step to fill this gap.
However, the combinatorial output of the decomposition is still large. Thus, we particularly regard our work as key ingredient for querying information on and constructing geometric objects from a small set of surfaces. Examples are meshing of single surfaces, the computation of space-curves defined by two surfaces, computation of lower envelopes of surfaces, or as a basic step to compute an efficient representation of a full three-dimensional arrangement. We also consider to use our analyses for (rotational) robot motion planning.
|
|
|
