An efficient algorithm for the stratification and triangulation of an algebraic surface

We present a method to compute the exact topology of a real algebraic surface $S$, implicitly given by a polynomial $f\in\mathbb{Q}[x,y,z]$ of arbitrary total degree~$N$. Additionally, our analysis provides geometric information as it supports the computation of arbitrary precise samples of $S$ including critical points. We compute a stratification $\Omega_S$ of $S$ into $O(N^5)$ nonsingular cells, including the complete adjacency information between these cells. This is done by a projection approach. We construct a special planar arrangement $\mathcal{A}_S$ with fewer cells than a cad in the projection plane. 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. Based on $\Omega_S$ we also compute a simplicial complex which is isotopic to~$S$. A complete C++-implementation of the stratification algorithm is presented. It shows good performance for many well-known examples from algebraic geometry