Optimal Curve Straightening is ∃ℝ-Complete

We prove that the following problem has the same computational complexity as the existential theory of the reals: Given a generic self-intersecting closed curve γ in the plane and an integer m, is there a polygon with m vertices that is isotopic to γ? Our reduction implies implies two stronger results, as corollaries of similar results for pseudoline arrangements. First, there are isotopy classes in which every m-gon with integer coordinates requires exp(Ω(m)) bits of precision. Second, for any semi-algebraic set V, there is an integer m and a closed curve γ such that the space of all m-gons isotopic to γ is homotopy equivalent to V.

Optimal curve straightening is ∃ℝ-complete