Optimal Curve Straightening is $\exists \mathbb{R}$-Complete

Jeff Erickson

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 $\gamma$ in the plane an…