An improved complexity bound for computing the topology of a real algebraic space curve (Q6543074)

As far as I know, this work represents a big leap in calculating the topology of a space curve.\N\NIn the last few years, several articles have appeared studying the topology of a real algebraic space curve via projections and liftings. Recall that a real algebraic space curve \(C\) is defined as the intersection of two surfaces, defined by their respective implict equations. For example, in [\textit{D. N. Daouda} et al., in: Proceedings of the 2008 international symposium on symbolic and algebraic computation, ISSAC 2008, Linz/Hagenberg, Austria, July 20--23, 2008. New York, NY: Association for Computing Machinery (ACM). 47--54 (2008; Zbl 1238.14046)], the space curve is required to be in pseudo generic position. Recall that a space curve is said to be in pseudo generic position with respect to the \((x,y)\) plane if the projection \(\Pi_z\) is injective up to a finite number of exceptions. In addition, in the same paper, an algorithm was introduced for computing the topology of a space curve when not only the curve is in a generic position but the projection is in general position. In [\textit{J. G. Alcázar} and \textit{J. R. Sendra}, J. Symb. Comput. 39, No. 6, 719--744 (2005; Zbl 1120.14049)], the conditions are even stronger. \N\NHowever, in this work, the authors only require sweep generic position in the \(x\)-direction, i.e., they require that the curve \(C\) has no asymptote in the \(z\)-direction and a finite number of points on any \(x\)-fiber plane \(\{x = \alpha\}\) for \(\alpha \in R\). If this is not the case, it is possible to achieve such a condition by applying shearings of the coordinate system. Thus, the required condition is weaker, but this has a price; the lifting process. The authors introduce a new technique to achieve the lifting step, which recovers points of the space curve in each plane fiber from several projections. This step might not be efficient if it requires many sheared projections. The algorithm is described in detail in Section 3, and the bit complexity of the algorithm is given in Section 4.2.