A note on the complexity of real algebraic hypersurfaces
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.
- Some aspects of complexity in real algebraic geometry
- Smoothing of real algebraic hypersurfaces by rigid isotopies
- An improved upper complexity bound for the topology computation of a real algebraic plane curve
- Isotopic triangulation of a real algebraic surface
- Computing the real isolated points of an algebraic hypersurface
- Algorithms in real algebraic geometry
- All 2-manifolds have finitely many minimal triangulations
- An efficient algorithm for the stratification and triangulation of an algebraic surface
- Effective computational geometry for curves and surfaces
- Fast and exact geometric analysis of real algebraic plane curves
- scientific article; zbMATH DE number 1354817 (Why is no real title available?)
- scientific article; zbMATH DE number 1027930 (Why is no real title available?)
- scientific article; zbMATH DE number 1433426 (Why is no real title available?)
- Irreducible triangulations of the torus
- Isotopic triangulation of a real algebraic surface
- Note on irreducible triangulations of surfaces
- On the asymptotic and practical complexity of solving bivariate systems over the reals
- On the topology of planar algebraic curves
- Smoothing of real algebraic hypersurfaces by rigid isotopies
- Algebraicity of real analytic hypersurfaces and blowing-down.
- Complexity of intersections of real quadrics and topology of symmetric determinantal varieties
- scientific article; zbMATH DE number 4014881 (Why is no real title available?)
- scientific article; zbMATH DE number 4177284 (Why is no real title available?)
- scientific article; zbMATH DE number 1023365 (Why is no real title available?)
- What is the degree of a smooth hypersurface?
- SqFreeEVAL: An (almost) optimal real-root isolation algorithm
- On the intrinsic complexity of point finding in real singular hypersurfaces
This page was built for publication: A note on the complexity of real algebraic hypersurfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659701)
