# Item

ITEM ACTIONSEXPORT

Released

Journal Article

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

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Berberich, E., Kerber, M., & Sagraloff, M. (2010). An efficient algorithm for the
stratification and triangulation of an algebraic surface.* Computational Geometry: Theory and Applications,*
*43*(3), 257-278. doi:10.1016/j.comgeo.2009.01.009.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1805-1

##### 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.