Real Algebraic and Analytic Geometry Preprint Server

e-mail:
homepage: http://math.unice.fr/~comte/

Submission: 2004, November 24.

Abstract:
In this paper, we present a new algorithm to mesh surfaces defined by an implicit equation, which is able to isolate the singular points of the surface, to guaranty the topology in the smooth part, while producing a number of linear pieces, related to geometric invariants of the surface. We prove its termination and correctness and give complexity bounds, based on entropy analysis. The method applies to surfaces defined by a polynomial equation or a spline equation. We use Bernstein bases to represent the function in a box and subdivide this representation according to a generalization of Descartes rule, until the problem in each box boils down to the case where either the implicit object is isotopic to its linear approximation in the cell or the size of the cell is smaller than a parameter $\epsilon $. This ensures that the topology of the implicit surface is cached within a precision $\epsilon $. Experimentations on classical examples from the classification of singularities show the eciency of the approach.

Full text, 15p.: pdf 297k.