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

作者：Berberich Eric; Kerber Michael; Sagraloff Michael^*

来源：Computational Geometry-Theory and Applications, 2010, 43(3): 257-278.

DOI：10.1016/j.comgeo.2009.01.009

• Algebraic surfaces
• Exact geometric computation
• Topology computation
• Cylindrical algebraic decomposition

We present a method to compute the exact topology of a real algebraic surface S, implicitly given by a polynomial f is an element of 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) non-singular cells, including the complete adjacency information between these cells. This is done by a projection approach. We construct a special planar arrangement 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.

• 出版日期2010-4