logo

Isotop

Isotop is a Maple software for computing the topology/isotopy of an implicit algebraic plane curve, that is, for computing an arrangement of polylines isotopic to the input curve. It also provides a new solution to the important problem of plotting such curves in a certified way, that is -- in particular -- without missing connected components, singular points, etc. This problem is also a necessary key step for computing arrangements of algebraic curves.

Previous methods based on the cylindrical algebraic decomposition (CAD) use subresultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to use Grobner basis computations and isolation with rational univariate representations for computing critical points. Unlike previous approaches, our approach requires neither generic position, nor shearing the coordinate system when the input curve is not in generic position. Furthermore, it has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. These choices also induce different methods for computing multiplicities in systems and in fibers. Our algorithm isolates critical points in boxes and computes a decomposition of the plane (which is not a CAD) by rectangular boxes. This decomposition also induces a new approach for computing an arrangement of polylines isotopic to the input curve.

Our preliminary implementation is competitive with other state-of-the-art implementations. It performs similarly for small-degree curves and performs signifficantly better for higher-degrees, in particular when the curves are not in generic position, as the results of our tests show.

You can also download Isotop or try it online using our server.

References
[1] J. Cheng, S. Lazard, L. Peñaranda, M. Pouget, F. Rouillier, E. Tsigaridas. On the topology of planar algebraic curves. In Proc. of the 25th annual Symposium on Computational Geometry (SoCG'09), pp. 361-370, Århus, Denmark, 2009. pdf