A worst-case bound for topology computation of algebraic curves (Q765857): Difference between revisions

The authors improve a previous efficiency bound on topology computation of plane algebraic curves. This improvement comes not from a novel general approach (they claim it is the same as [\textit{L. Gonzalez-Vega} and \textit{I. Necula}, ``Efficient topology determination of implicitly defined algebraic plane curves'', Comput. Aided Geom. Des. 19, No. 9, 719--743 (2002; Zbl 1043.68105)]. Instead, it is derived from improvements in real root isolation [\textit{M. Sagraloff}, ``On the complexity of real root isolation'', \url{arXiv:1011.0344}] and subsequent refinement [\textit{M. Kerber} and \textit{M. Sagraloff}, ``Root refinement for real polynomials'', \url{arXiv:1004.1362}], plus the use of amortized analysis: the bound for the complexity of isolating all fiber polynomials is usually the same as the worst-case bound for a single fiber (the technique is extensively used in [\textit{M. Kerber}, Geometric algorithms for algebraic curves and surfaces. Ph.D. Thesis, Universität des Saarlandes, Germany (2009)] and [\textit{A. Eigenwillig, M. Kerber} and \textit{N. Wolpert}, ``Fast and exact geometric analysis of real algebraic plane curves'', ISSAC 2007. Proceedings of the 32nd international symposium on symbolic and algebraic computation (ISSAC 2007), Waterloo, ON, Canada, July 29--August 1, 2007. New York, NY: Association for Computing Machinery (ACM). 151--158 (2007; Zbl 1190.14062)] according to the authors).