Fetching the paper…
Reading the bibliography…
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 and an integer $m$, is there a polygon with $m$ vertices that is isotopic to $\gamma$? Our reduction implies implies two stronger results, as corollaries of similar results for pseudoline arrangements.
Min-cost flow in unit-capacity planar graphs
Adam Karczmarz and Piotr Sankowski · 1907
Earlier work this paper cites.
A universality theorem for nested polytopes
Michael G. Dobbins, Andreas Holmsen, and Tillman Miltzow · 1908
Earlier work this paper cites.
Die teilung der projektiven ebene durch gerade und pseudogerade
Friedrich Levi · 1926
Earlier work this paper cites.
Teilungen der Ebene durch Geraden oder topologische Geraden
Gerhard Ringel · 1956
Earlier work this paper cites.
A census of planar maps
William T. Tutte · 1963
Earlier work this paper cites.
Arrangements and Spreads
Branko Grünbaum · 1972
Earlier work this paper cites.
Finding the intersection of two convex polyhedra
David E. Muller and Franco P. Preparata · 1978
Earlier work this paper cites.
Proof of a conjecture of Burr, Grünbaum, and Sloane
Jacob E. Goodman · 1980
Earlier work this paper cites.
Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines
Jacob E. Goodman and Richard Pollack · 1980
Earlier work this paper cites.
Classification of knot projections
Clifford H. Dowker and Morwen B. Thistlethwaite · 1983
Earlier work this paper cites.
Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams
Leonidas J. Guibas and Jorge Stolfi · 1985
Earlier work this paper cites.
Varieties of combinatorial types of projective configurations and convex polyhedra
Nikolai E. Mnëv · 1985
Earlier work this paper cites.
Edge-based data structures for solid modeling in curved-surface environments
Kevin Weiler · 1985
Earlier work this paper cites.
On embedding a graph in the grid with the minimum numberof bends
Roberto Tamassia · 1987
Earlier work this paper cites.
Some algebraic and geometric computations in PSPACE
John Canny · 1988
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
Nikolai E. Mnëv · 1988
Earlier work this paper cites.
Computational Synthetic Geometry
Jürgen Bokowski and Bernd Sturmfels · 1989
Earlier work this paper cites.
Coordinate representation of order types requires exponential storage
Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels · 1989
Earlier work this paper cites.
Kombinatorische Realisierbarkeitskriterien für orientierte Matroide
Jürgen Richter · 1989
Earlier work this paper cites.
The intrinsic spread of a configuration in 𝐑 d \mathbf{R}^{d}
Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels · 1990
Earlier work this paper cites.
Some provably hard crossing number problems
Daniel Bienstock · 1991
Earlier work this paper cites.
Classifying immersed curves
J. Scott Carter · 1991
Earlier work this paper cites.
Stretchability of pseudolines is NP-hard
Peter W. Shor · 1991
Cited alongside, same era.
On the computational complexity and geometry of the first-order theory of the reals, Part I
James Renegar · 1992
Cited alongside, same era.
Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
Joel E. Cohen and Uriel G. Rothblum · 1993
Cited alongside, same era.
Intersection graphs of segments
Jan Kratochvíl and Jiří Matoušek · 1994
Cited alongside, same era.
Mnëv’s universality theorem revisited
Jürgen Richter-Gebert · 1995
Cited alongside, same era.
Realization spaces of polytopes
Jürgen Richter-Gebert · 1996
Cited alongside, same era.
Algorithmic graph embeddings
Integer realizations of disk and segment graphs
Colin McDiarmid and Tobias Müller · 2013
Later among the works it cites.
Realizability of graphs and linkages
Marcus Schaefer · 2013
Later among the works it cites.
Intersection graphs of segments and ∃ R \exists\mdmathbb{R}
Jiří Matoušek · 2014
Later among the works it cites.
Delaunay triangulations with disconnected realization spaces
Arnau Padrol and Louis Theran · 2014
Later among the works it cites.
Universality theorems for inscribed polytopes and Delaunay triangulations
Karim A. Adiprasito, Arnau Padrol, and Louis Theran · 2015
Later among the works it cites.
The complexity of computing the minimum rank of a sign pattern matrix
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jianer Chen · 1997
Cited alongside, same era.
Complexity and Real Computation
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale · 1998
Cited alongside, same era.
Oriented Matroids , second edition
Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler · 2000
Cited alongside, same era.
Universality theorems for configuration spaces of planar linkages
Michael Kapovich and John J. Millson · 2002
Cited alongside, same era.
Properties of arrangement graphs
Prosenjit Bose, Hazel Everett, and Stephen Wismath · 2003
Cited alongside, same era.
Algorithms in Real Algebraic Geometry , 2nd edition
Saugata Basu, Richard Pollack, and Marie-Françoise Roy · 2006
Cited alongside, same era.
Amey Bhangale and Swastik Kopparty · 2015
Later among the works it cites.
Computational geometry column 62
Jean Cardinal · 2015
Later among the works it cites.
The complexity of simultaneous geometric graph embedding
Jean Cardinal and Vincent Kusters · 2015
Later among the works it cites.
A catalog of ∃ R \exists\mdmathbb{R} -complete decision problems about Nash equilibria in multi-player games
Vittorio Bilò and Marios Mavronicolas · 2016
Later among the works it cites.
∃ R \exists\mdmathbb{R} -complete decision problems about symmetric Nash equilibria in symmetric multi-player games
Vittorio Bilò and Marios Mavronicolas · 2017
Later among the works it cites.
Recognition and complexity of point visibility graphs
Jean Cardinal and Udo Hoffmann · 2017
Later among the works it cites.
The complexity of drawing graphs on few lines and few planes
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff · 2017
Later among the works it cites.
Psuedoline arrangements
Stefan Felsner and Jacob E. Goodman · 2017
Later among the works it cites.
On the complexity of the planar slope number problem
Udo Hoffmann · 2017
Later among the works it cites.
Recognising multidimensional euclidean preferences
Dominik Peters · 2017
Later among the works it cites.
Fixed points, Nash equilibria, and the existential theory of the reals
Marcus Schaefer and Daniel Štefankovič · 2017
Later among the works it cites.
The nonnegative rank of a matrix: Hard problems, easy solutions
Yaroslav Shitov · 2017
Later among the works it cites.
The art gallery problem is ∃ R \exists\mdmathbb{R} -complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow · 2018
Later among the works it cites.
Intersection graphs of rays and grounded segments
Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber · 2018
Later among the works it cites.
∃ R \exists\mdmathbb{R} -completness for decision version of multi-player (symmetric) Nash equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod · 2018
Later among the works it cites.
Marcus Schaefer and Daniel Štefankovič · 2018
Later among the works it cites.