A note on the complexity of real algebraic hypersurfaces (Q659701)

This paper deals with the complexity of the computation of simplicial complexes in \(\mathbb{R}^d\) which are isotopic to real algebraic hypersurfaces in \(\mathbb{R}^d\). The author shows that in the case of curves in \(\mathbb{R}^d\), any stable isocomplex (i.e. a complex that is stable at its vertices) can be made with \(\mathcal{O}(n^3)\) cells, \(n\) being the degree of the curve isotopic to the simplicial complex. Examples of curves where the number of vertices needed are of the order of \(\Omega(n^3)\) are also presented, so this can be considered as a sharp result. Then the author shows that if one removes the stability condition, than one can construct an isocomplex with \(\mathcal{O}(n^2)\) vertices. Again, this bound is shown to be sharp. For general \(d\geq2\), it is shown that there are algebraic hypersurfaces in \(\mathbb{R}^d\) of degree \(n\) such that any stable isocomplex on them has \(\Omega(n^{d+1})\) vertices. In this case, however, this lower bound cannot be attained. Instead, the author shows how to produce stable isocomplexes with \(\mathcal{O}(n^{2^d-1})\) simplices, and an isocomplex with \(\mathcal{O}(n^{3/4\,2^d-1})\) cells in the case the hypersurface is compact. It is conjectured that this bound is not sharp.