de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44118

Berberich,  Eric
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44759

Kerber,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45332

Sagraloff,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.