hide
Free keywords:
-
Abstract:
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.
