Isotop

Isotop is a Maple software for computing the topology of an algebraic plane curve, that is, for computing an arrangement of polylines isotopic to the input curve. This problem is a necessary key step for computing arrangements of algebraic curves and has also applications for curve plotting. This software was developed in collaboration between Vegas (Nancy, France) and Salsa (Paris, France). It is based on the method described in [1] which incorporates several improvements over previous methods. In particular, our approach does not require generic position (nor shearing) and avoids the computations of sub-resultant sequences.

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 replace these tools by Gröbner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. These choices 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. Chen, S. Lazard, L. Peñaranda, M. Pouget, F. Rouillier, E. Tsigaridas. On the topology of planar algebraic curves. Proc. of the 24th European Workshop on Computational Geometry, Nancy, France. Pages 213-216. 2008.