Optimal Curve Straightening is -Complete
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 integer , is there a polygon with 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 -gon with integer coordinates requires bits of precision. Second, for any semi-algebraic set , there is an integer and a closed curve such that the space of all -gons isotopic to is homotopy equivalent to .
arXiv comment17 pages, 10 figures (v2 fixes a utf8 encoding issue)
References in corpus (6)
- Recognition and Complexity of Point Visibility Graphs
- The complexity of computing the minimum rank of a sign pattern matrix
- Mnev-Sturmfels universality for schemes
- The Art Gallery Problem is -complete
- A Universality Theorem for Nested Polytopes
- Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines