scientific article; zbMATH DE number 16645
[For the entire collection see Zbl 0721.00009.] During the last years several researchers have considered the problem of finding polynomial-time sequential algorithms for the computation of the topology of a real algebraic plane curve. The authors divide these algorithms into two main groups: those coding real algebraic numbers by means of isolating intervals and those coding them à la Thom. The aim of this note is to survey the state of the art as far as the second group is concerned. In particular, the authors introduce two new algorithms, the algorithm computing the topology of a real algebraic plane curve with the lowest running time, while the other one has been successfully implemented. Recently, it has been noted that the ground algorithm used to code real algebraic numbers à la Thom has a complexity smaller than the one used for the complexity estimates given by \textit{M. F. Roy}. In the first part of this note the authors give a proof of this fact and, using it, they obtain new upper bounds for the running times of the auxiliary procedures introduced by Roy, and which they use in their algorithms. Notice that, in both cases, the running times are much lower than those of the corresponding fastest algorithms using isolating intervals. In the second part of this note the authors introduce some modifications to Roy's algorithms, obtaining: (i) an algorithm \(\text{CAD}_ 0\); (ii) an algorithm \(\text{TOP}_ 0\); and (iii) another algorithm for the computation of the topology, \(\text{TOP}_ 2\). They conclude that \(\text{CAD}_ 0\) is the fastest algorithm computing an \(F\)-invariant c.a.d. of \(R^ 2\), while \(\text{TOP}_ 0\) is the fastest algorithm computing the topology of \(C\). They remark that, although these all are similar in spirit, there is a great difference between Roy's algorithm and \(\text{TOP}_ 2\) on one side, and \(\text{CAD}_ 0\) and \(\text{TOP}_ 0\) on the other side: while the first ones freely use points of the real spectrum of \(R[X,Y]\), the second ones only use real algebraic numbers to get the same information.
- Determinantal formulae for the solution set of zero-dimensional ideals
- NC algorithms for real algebraic numbers
- Construction of roadmaps in semi-algebraic sets
- Dynamic evaluation and real closure.
- An efficient method for analyzing the topology of plane real algebraic curves.
- Efficient topology determination of implicitly defined algebraic plane curves.
- Real plane algebraic curves.
- Algorithms to compute the topology of orientable real algebraic surfaces
- On the realization problem of real algebraic plane curves as Hessian curves
- Computing the topology of a real algebraic plane curve whose defining equations are available only ``by values
- Topology of real algebraic space curves
- On algorithms to obtain linear determinantal representations of smooth plane curves of higher degree
- An algorithm for isolating the real solutions of piecewise algebraic curves
- Algorithm 976
- Computing totally real hyperplane sections and linear series on algebraic curves
- scientific article; zbMATH DE number 4183588 (Why is no real title available?)
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- A weak version of the Blum, Shub, and Smale model
- A worst-case bound for topology computation of algebraic curves
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3973331)
