Fetching the paper…
Reading the bibliography…
Consider an ordered point set $P = (p_1,\ldots,p_n)$, its order type (denoted by $\chi_P$) is a map which assigns to every triple of points a value in $\{+,-,0\}$ based on whether the points are collinear(0), oriented clockwise(-) or counter-clockwise(+).
Discrete dynamic programming and capital allocation
George L. Nemhauser and Zev Ullmann · 1969
Earlier work this paper cites.
How good is the simplex algorithm
Victor Klee and George J. Minty · 1970
Earlier work this paper cites.
Arrangements and Spreads
B. Grünbaum and Conf. Board of the Mathematical Sciences · 1972
Earlier work this paper cites.
Solving systems of polynomial inequalities in subexponential time
D. Yu. Grigor’ev and N. N. Vorobjov, Jr · 1988
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
Nicolai E Mnëv · 1988
Earlier work this paper cites.
Coordinate representation of order types requires exponential storage
J. E. Goodman, R. Pollack, and B. Sturmfels · 1989
Earlier work this paper cites.
Stretchability of pseudolines is np-hard
Peter Shor · 1991
Earlier work this paper cites.
Axioms and hulls
Donald Ervin Knuth · 1992
Earlier work this paper cites.
Mnëv’s universality theorem revisited
Jürgen Richter-Gebert · 1995
Earlier work this paper cites.
Realization spaces of 4-polytopes are universal
Jürgen Richter-Gebert and Günter M. Ziegler · 1995
Earlier work this paper cites.
Günter M Ziegler · 1996
Earlier work this paper cites.
On the number of arrangements of pseudolines
Stefan Felsner · 1997
Earlier work this paper cites.
Oriented matroids
Anders Bjorner, Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M Ziegler · 1999
Earlier work this paper cites.
Random knapsack in expected polynomial time
René Beier and Berthold Vöcking · 2003
Earlier work this paper cites.
Pseudoline arrangements
Jacob E Goodman · 2004
Earlier work this paper cites.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel A. Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method
David Arthur and Sergei Vassilvitskii · 2006
Cited alongside, same era.
Typical properties of winners and losers in discrete optimization
René Beier and Berthold Vöcking · 2006
Cited alongside, same era.
Worst case and probabilistic analysis of the 2-opt algorithm for the tsp
Matthias Englert, Heiko Röglin, and Berthold Vöcking · 2007
Cited alongside, same era.
Sphere and dot product representations of graphs
Ross J. Kang and Tobias Müller · 2011
Cited alongside, same era.
Extreme point and halving edge search in abstract order types
Oswin Aichholzer, Tillmann Miltzow, and Alexander Pilz · 2013
6: Oriented matroids
Jürgen Richter-Gebert and Günter M Ziegler · 2017
Later among the works it cites.
Fixed points, nash equilibria, and the existential theory of the reals
Marcus Schaefer and Daniel Stefankovic · 2017
Later among the works it cites.
The art gallery problem is ∃ ℝ \exists\mathbb{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.
A friendly smoothed analysis of the simplex method
Daniel Dadush and Sophie Huiberts · 2018
Later among the works it cites.
On order types of random point sets
Olivier Devillers, Philippe Duchon, Marc Glisse, and Xavier Goaoc · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Christian Herrmann, Johanna Sokoli, and Martin Ziegler · 2013
Cited alongside, same era.
Realizability of graphs and linkages
Marcus Schaefer · 2013
Cited alongside, same era.
Intersection graphs of segments and ∃ ℝ \exists\mathbb{R}
Jiří Matoušek · 2014
Cited alongside, same era.
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod · 2015
Cited alongside, same era.
A universality theorem for nonnegative matrix factorizations
Yaroslav Shitov · 2016
Cited alongside, same era.
Recognition and complexity of point visibility graphs
Jean Cardinal and Udo Hoffmann · 2017
Cited alongside, same era.
Later among the works it cites.
∀ ∃ ℝ \forall\exists\mathbb{R} -completeness and area-universality
Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rza̧żewski · 2018
Later among the works it cites.
Smoothed analysis of the art gallery problem
Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow · 2018
Later among the works it cites.
The complexity of drawing a graph in a polygonal region
Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal · 2018
Later among the works it cites.
Smoothed Complexity and Pseudopolynomial-Time Algorithms
Tim Roughgarden · 2018
Later among the works it cites.
Tim Roughgarden · 2018
Later among the works it cites.
The complexity of tensor rank
Marcus Schaefer and Daniel Stefankovic · 2018
Later among the works it cites.
Minicourse on smoothed analysis
Heiko Röglin · 2019
Closest in time.
Smoothed order types
Martijn van Schaik · 2019
Closest in time.