A certified numerical algorithm for the topology of resultant and discriminant curves (Q346543): Difference between revisions

Let \(\mathcal C\) be a real plane algebraic curve defined by the resultant of two polynomials (resp., by the discriminant of a polynomial). Geometrically such a curve is the projection of the intersection of the surfaces defined implicitly by the equations \(P(x,y,z)=Q(x,y,z)=0\) (resp. \(P(x,y,z)=\frac{\partial P}{\partial z}(x,y,z)=0\)), and generically its singularities are nodes (resp. nodes and ordinary cusps). In the previous literature, one may find numerical algorithms that compute the topology of smooth curves but usually fail to certify the topology of singular ones. The main challenge is to find practical numerical criteria that guarantee the existence and the uniqueness of a singularity inside a given box \(B\), while ensuring that \(B\) does not contain any closed loop of \(\mathcal C\). The authors solve this problem by first providing a square deflation system, based on subresultants, that can be used to certify numerically whether \(B\) contains a unique singularity \(p\) or not. Then, it is introduced a numeric adaptive separation criterion based on interval arithmetic to ensure that the topology of \(\mathcal C\) in \(B\) is homeomorphic to the local topology at \(p\). The algorithms presented are implemented and experiments show their efficiency compared to previous symbolic or homotopic methods.