🔥 Preprint, August 2018.

arXiv:1908.09400

Abstract:

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 integerm, is there a polygon withmvertices 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 everym-gon with integer coordinates requires exp(Ω(m)) bits of precision. Second, for any semi-algebraic setV, there is an integermand a closed curve γ such that the space of allm-gons isotopic to γ is homotopy equivalent toV.

Publications - Jeff Erickson (jeffe@illinois.edu) 27 Aug 2019