On the complexity of computing the topology of real algebraic space curves (Q2661918): Difference between revisions

In this paper, a new deterministic algorithm to compute the topology of an algebraic space curve is presented. Determining the topology of algebraic curves in the space often requires that they be in a generic position. This is difficult to verify, and there are many works in the literature addressing this task. The main goals of the paper are, following the ideas of \textit{J.-S. Cheng} and \textit{K. Jin} [Lect. Notes Comput. Sci. 8660, 74--84 (2014; Zbl 1416.68214)], first to put the algebraic space curve in a generic position and then, to compute the topology using an algorithm, different from previous work, that is a modified version of another algorithm presented in [\textit{K. Jin} and \textit{J.-S. Cheng}, in: Proceedings of the 2014 symposium on symbolic-numeric computation, SNC 2014, Shanghai, China, July 28--31, 2014. New York, NY: Association for Computing Machinery (ACM). 118--127 (2014; Zbl 1345.68262)]. Finally, the bit complexity of the algorithm is also analyzed. As the authors claim in the abstract, ``the bit complexity is \(\tilde{\mathcal{O}}(N^{20})\), where \(N = \max\left\{d, \tau\right\}\), \(d\) and \(\tau\) are the degree bound and the bit size bound of the coefficients of the defining polynomials of the algebraic space curve; being, currently, the best bound among the existing work and gaining the existing results at least \(N^2\)''.