Fast Isotopy Computation for T-Curves
This work addresses the computational bottleneck in enumerating real schemes for algebraic curves, enabling exhaustive analysis at scale, though it is incremental as it builds on Viro's Patchworking Theorem.
The authors tackled the problem of efficiently determining the ambient isotopy type of smooth real plane projective algebraic curves from T-curves, achieving a near-quadratic time algorithm that enables computing billions of real schemes per second with GPU acceleration, as demonstrated by enumerating all 121 real schemes of degree seven.
A T-curve of degree $d$ is given by a regular unimodular triangulation of $d \cdot Î_2$ together with a sign distribution on its lattice points. By Viro's Patchworking Theorem, this determines the ambient isotopy type (a.k.a. real scheme) of a smooth real plane projective algebraic curve of the same degree. We present a near-quadratic time algorithm for extracting that isotopy type from the triangulation and the signs. Through a GPU-accelerated implementation, this allows one to compute billions of real schemes per second, enabling exhaustive enumeration at scale. This algorithm was essential for our recent construction of all 121 real schemes of degree seven by T-curves.