pith. sign in

arxiv: 1907.04645 · v1 · pith:LFTCKC6Jnew · submitted 2019-07-10 · 💻 cs.CG · cs.CC· cs.DM· cs.DS· math.CO

Smoothed Analysis of Order Types

Ivor van der Hoog , Tillmann Miltzow , Martijn van Schaik This is my paper

Pith reviewed 2026-05-24 23:28 UTC · model grok-4.3

classification 💻 cs.CG cs.CCcs.DMcs.DSmath.CO
keywords order typessmoothed analysispoint set realizabilityexistential theory of the realscomputational geometryabstract order typesperturbed point sets
0
0 comments X

The pith

Smoothed analysis reduces order type realizability to expected NP time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

An abstract order type assigns an orientation or collinearity to every triple of n labeled points, provided the assignment is consistent when restricted to any five points. Deciding whether such an assignment arises from some actual point set in the plane is complete for the existential theory of the reals in the worst case. The paper replaces arbitrary inputs with inputs obtained by adding small continuous random noise to the coordinates of any point set and proves that realizability can then be decided by an algorithm whose expected running time lies in NP. This shows that the known hardness is an artifact of highly artificial inputs rather than of inputs that arise after realistic perturbation.

Core claim

Under the standard smoothed-analysis model of small random continuous perturbations applied to point coordinates, the problem of deciding whether a given abstract order type is realizable by a point set lies in expected NP time, whereas the same decision problem is ∃R-complete without the perturbation model.

What carries the argument

The smoothed-analysis noise model on point sets, which turns worst-case ∃R-complete order-type realizability into a problem solvable in expected NP time.

If this is right

  • Order-type realizability becomes tractable for all inputs that arise from perturbed point sets.
  • The ∃R-completeness result does not govern the complexity of the problem on smoothed inputs.
  • Recognition algorithms can be analyzed with respect to their expected performance under coordinate noise rather than their worst-case behavior.
  • This supplies one of the first examples of an ∃R-complete geometric problem whose smoothed complexity is markedly lower than its worst-case complexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar smoothed-analysis arguments may place other ∃R-complete problems in computational geometry into expected NP time.
  • Practical systems that rely on order-type information, such as visibility or motion-planning routines, can assume that noisy input instances will not trigger the worst-case hardness.
  • Algorithm designers may profitably shift attention from worst-case exponential-time methods to methods whose expected performance is polynomial or NP-bounded once noise is present.

Load-bearing premise

That realistic point-set instances are adequately modeled by adding small continuous random perturbations to the coordinates of an arbitrary point set.

What would settle it

A family of abstract order types for which the expected running time of any recognition algorithm remains superpolynomial even after the standard smoothed perturbation is applied.

Figures

Figures reproduced from arXiv: 1907.04645 by Ivor van der Hoog, Martijn van Schaik, Tillmann Miltzow.

Figure 1
Figure 1. Figure 1: A configuration that describes the possible orientations of triples of points: the orientation of [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The configuration used in Pappus’ hexagon theorem: when [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The instance P = {p, q, r} is randomly perturbed to Px = {px, qx, rx}. The set Px is snapped to the points P 0 = {p 0 , q0 , r0}. Cost functions. There are three natural ways to define the “cost” of realizing the order type of a real-valued point set P. The first is the grid width w = w(P), which is the largest value w ∈ [0, 1], such that snapping P onto a grid of width w preserves the order type of P. The… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the proof of Lemma 4. The green segment indicates the location of [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The intersection area of the perturbation disk and the area induced by the other two points is [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Rewriting the sums. A Poof of Lemma 5 Lemma 5. Given a function f : Ω → {1, . . . , b} and assume that Pr(f(x) > b) = 0. Then it holds that E[f] = X b z=1 z Pr(f(x) = z) = X b z=1 Pr(f(x) ≥ z). Proof. To simplify notation, we write g(z) = Pr(f(x) = z). We can now write the expectation as E(f) = X b z=1 z Pr(f(x) = z) = X b z=1 zg(z) = X b z=1 Xz t=1 g(z) For the next step, we refer to [PITH_FULL_IMAGE:fig… view at source ↗
read the original abstract

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(+). An abstract order type is a map $\chi : \left[\substack{n\\3}\right] \rightarrow \{+,-,0\}$ (where $\left[\substack{n\\3}\right]$ is the collection of all triples of a set of $n$ elements) that satisfies the following condition: for every set of five elements $S\subset [n]$ its induced order type $\chi_{|S}$ is realizable by a point set. To be precise, a point set $P$ realizes an order type $\chi$,if $\chi_P(p_i,p_j,p_k) = \chi(i,j,k)$, for all $i<j<k$. Planar point sets are among the most basic and natural geometric objects of study in Discrete and Computational Geometry. Properties of point sets are relevant in theory and practice alike. It is known, that deciding if an abstract order type is realizable is complete for the existential theory of the reals. Our results show that order type realizability is much easier for realistic instances than in the worst case. In particular, we can recognize instances in "expected \NP-time". This is one of the first $\exists\mathbb{R}$-complete problems analyzed under the lens of Smoothed Analysis.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript analyzes order type realizability under smoothed analysis. It defines abstract order types as combinatorial maps on triples satisfying local realizability on every 5-point subset, notes that global realizability is ∃R-complete, and claims that under the standard smoothed model (small random perturbations to an arbitrary point set) the problem becomes solvable in expected NP time, making it much easier for realistic instances than in the worst case. This is presented as one of the first ∃R-complete problems subjected to smoothed analysis.

Significance. If the central claim were to hold without the distributional issue identified below, the result would be significant as an early smoothed-analysis treatment of an ∃R-complete geometric decision problem, potentially indicating that perturbation models make such problems tractable in practice.

major comments (1)
  1. [Abstract] Abstract: The smoothed-analysis noise model perturbs an arbitrary point set, which by construction yields a realizable order type χ. Under the induced distribution the input is always a yes-instance of the realizability decision problem. Consequently any algorithm that unconditionally outputs 'yes' solves the problem correctly in constant time (hence in expected NP time). The claim that recognition 'is much easier for realistic instances' and can be performed in 'expected NP-time' is therefore trivial unless the distribution is defined to place positive mass on non-realizable abstract order types or 'recognize' denotes a different task (e.g., constructing a realization). The abstract supplies no clarification that resolves this.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a substantive issue with the presentation of the smoothed model and the precise meaning of the claimed result. We agree that the abstract as written leads to a trivial interpretation and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The smoothed-analysis noise model perturbs an arbitrary point set, which by construction yields a realizable order type χ. Under the induced distribution the input is always a yes-instance of the realizability decision problem. Consequently any algorithm that unconditionally outputs 'yes' solves the problem correctly in constant time (hence in expected NP time). The claim that recognition 'is much easier for realistic instances' and can be performed in 'expected NP-time' is therefore trivial unless the distribution is defined to place positive mass on non-realizable abstract order types or 'recognize' denotes a different task (e.g., constructing a realization). The abstract supplies no clarification that resolves this.

    Authors: We acknowledge that the referee's observation is correct: under the standard smoothed model of perturbing an arbitrary point set, every generated order type is realizable by construction, so the pure decision problem is trivial. The abstract does not sufficiently clarify the intended task. We will revise the abstract (and relevant sections) to state explicitly that the result concerns the expected time, under this distribution, of an algorithm that constructs a geometric realization of the order type (or produces a short NP certificate for realizability). This interpretation makes the claim non-trivial, as finding the realization or certificate is the computationally meaningful step even though the decision is always affirmative. The revised text will also note that the distribution places all mass on realizable instances and will avoid the phrasing that suggests a non-trivial decision problem. revision: yes

Circularity Check

1 steps flagged

Smoothed model generates only realizable order types by construction, making recognition trivial

specific steps
  1. self definitional [Abstract]
    "Our results show that order type realizability is much easier for realistic instances than in the worst case. In particular, we can recognize instances in 'expected NP-time'. This is one of the first ∃R-complete problems analyzed under the lens of Smoothed Analysis."

    The smoothed-analysis noise model is defined by taking an arbitrary point set (hence a realizable order type) and applying small continuous random perturbations. The resulting order type χ is realized by the perturbed point set, so every input drawn from the distribution is realizable by construction. The recognition task therefore collapses to a constant-time 'always yes' procedure that is correct on all instances under the model. The claimed improvement in complexity is identical to this definitional property of the distribution.

full rationale

The paper's central claim is that realizability becomes 'much easier for realistic instances' and recognizable in 'expected NP-time' under smoothed analysis. However, the model defines realistic instances exclusively via perturbation of an existing point set. Every such instance is realizable by the perturbed points, so the decision problem has answer 'yes' with probability 1. Recognition therefore reduces to the constant-time algorithm that always outputs 'yes', which is correct on the entire support of the distribution. This matches the self-definitional pattern: the claimed complexity improvement is equivalent to the definition of the input distribution rather than an independent algorithmic result. No external verification or non-trivial decision task is required.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard smoothed-analysis perturbation model and on the known ∃R-completeness of order-type realizability; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Small continuous random perturbations applied independently to each point constitute a realistic model for input instances.
    Invoked to justify that the smoothed model captures practical cases.

pith-pipeline@v0.9.0 · 5830 in / 1110 out tokens · 19143 ms · 2026-05-24T23:28:18.220251+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 6 internal anchors

  1. [1]

    The Art Gallery Problem is $\exists \mathbb{R}$-complete

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃R- complete. In STOC 2018, pages 65–73, 2018. Arxiv 1704.06969. URL: http://doi.acm.org/10. 1145/3188745.3188868, doi:10.1145/3188745.3188868

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/3188745.3188868 2018

  2. [2]

    Extreme point and halving edge search in abstract order types

    Oswin Aichholzer, Tillmann Miltzow, and Alexander Pilz. Extreme point and halving edge search in abstract order types. Comput. Geom., 46(8):970–978, 2013. URL: https://doi.org/10.1016/ j.comgeo.2013.05.001, doi:10.1016/j.comgeo.2013.05.001

    work page doi:10.1016/j.comgeo.2013.05.001 2013

  3. [3]

    Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method

    David Arthur and Sergei Vassilvitskii. Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method. In FOCS 2016, pages 153–164. IEEE, 2006

    work page 2016

  4. [4]

    Random knapsack in expected polynomial time

    Ren´ e Beier and Berthold V¨ ocking. Random knapsack in expected polynomial time. InSTOC, pages 232–241. ACM, 2003

    work page 2003

  5. [5]

    Typical properties of winners and losers in discrete optimization

    Ren´ e Beier and Berthold V¨ ocking. Typical properties of winners and losers in discrete optimization. SIAM Journal on Computing , 35(4):855–881, 2006

    work page 2006

  6. [6]

    Oriented matroids

    Anders Bjorner, Anders Bj¨ orner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and G¨ unter M Ziegler. Oriented matroids. Cambridge University Press, 1999

    work page 1999

  7. [7]

    In- tersection graphs of rays and grounded segments

    Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. In- tersection graphs of rays and grounded segments. Journal of Graph Algorithms and Applications , 22:273–295, 2018

    work page 2018

  8. [8]

    Recognition and complexity of point visibility graphs

    Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. Discrete & Computational Geometry , 57(1):164–178, 2017

    work page 2017

  9. [9]

    A friendly smoothed analysis of the simplex method

    Daniel Dadush and Sophie Huiberts. A friendly smoothed analysis of the simplex method. In STOC, pages 390–403. ACM, 2018

    work page 2018

  10. [10]

    On order types of random point sets

    Olivier Devillers, Philippe Duchon, Marc Glisse, and Xavier Goaoc. On order types of random point sets. CoRR, abs/1812.08525, 2018

    work page arXiv 2018

  11. [11]

    Dobbins, Linda Kleist, Tillmann Miltzow, and Pawe l Rz¸ a˙ zewski.∀∃R-completeness and area-universality

    Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Pawe l Rz¸ a˙ zewski.∀∃R-completeness and area-universality. WG 2018, 2018. Arxiv 1712.05142

    work page arXiv 2018

  12. [12]

    Smoothed Analysis of the Art Gallery Problem

    Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow. Smoothed analysis of the art gallery problem. CoRR, abs/1811.01177, 2018. URL: http://arxiv.org/abs/1811.01177, arXiv: 1811.01177

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  13. [13]

    Worst case and probabilistic analysis of the 2-opt algorithm for the tsp

    Matthias Englert, Heiko R¨ oglin, and Berthold V¨ ocking. Worst case and probabilistic analysis of the 2-opt algorithm for the tsp. In SODA, pages 1295–1304, 2007

    work page 2007

  14. [14]

    Smoothed analysis of local search for the maximum-cut problem

    Michael Etscheid and Heiko R¨ oglin. Smoothed analysis of local search for the maximum-cut problem. ACM Transactions on Algorithms (TALG) , 13(2):25, 2017

    work page 2017

  15. [15]

    Fabila-Monroy and C

    R. Fabila-Monroy and C. Huemer. Order types of random point sets can be realized with small integer coordinates. In EGC 2017, pages 73–76, 2017

    work page 2017

  16. [16]

    On the number of arrangements of pseudolines

    Stefan Felsner. On the number of arrangements of pseudolines. Discrete & Computational Geometry, 18(3):257–267, 1997

    work page 1997

  17. [17]

    Pseudoline arrangements

    Stefan Felsner and Jacob E Goodman. Pseudoline arrangements. In Handbook of Discrete and Computational Geometry, pages 125–157. Chapman and Hall/CRC, 2017

    work page 2017

  18. [18]

    Vazirani, and Sadra Yazdanbod

    Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In ICALP 2015, pages 554–566, 2015. 12

    work page 2015

  19. [19]

    J. E. Goodman, R. Pollack, and B. Sturmfels. Coordinate representation of order types requires exponential storage. In Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC ’89, pages 405–410, New York, NY, USA, 1989. ACM. doi:10.1145/73007. 73046

    work page doi:10.1145/73007 1989

  20. [20]

    Pseudoline arrangements

    Jacob E Goodman. Pseudoline arrangements. In Handbook of Discrete and Computational Geometry. Chapman & Hall, 2004

    work page 2004

  21. [21]

    D. Yu. Grigor’ev and N. N. Vorobjov, Jr. Solving systems of polynomial inequalities in subexpo- nential time. J. Symb. Comput. , 5(1-2):37–64, 2 1988. doi:10.1016/S0747-7171(88)80005-1

    work page doi:10.1016/s0747-7171(88)80005-1 1988

  22. [22]

    Gr¨ unbaum and Conf

    B. Gr¨ unbaum and Conf. Board of the Mathematical Sciences.Arrangements and Spreads. Regional conference series in mathematics. Conference Board of the Mathematical Sciences, 1972

    work page 1972

  23. [23]

    Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines

    Christian Herrmann, Johanna Sokoli, and Martin Ziegler. Satisfiability of cross product terms is com- plete for real nondeterministic polytime blum-shub-smale machines.arXiv preprint arXiv:1309.1270, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  24. [24]

    Kang and Tobias M¨ uller

    Ross J. Kang and Tobias M¨ uller. Sphere and dot product representations of graphs. InSoCG, pages 308–314. ACM, 2011

    work page 2011

  25. [25]

    Victor Klee and George J. Minty. How good is the simplex algorithm. Technical report, Washington Univ. Seattle Dept. of Mathematics, 1970

    work page 1970

  26. [26]

    Axioms and hulls , volume 606

    Donald Ervin Knuth. Axioms and hulls , volume 606. Springer, 1992

    work page 1992

  27. [27]

    The complexity of drawing a graph in a polygonal region

    Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The complexity of drawing a graph in a polygonal region. Arxiv, 2018. Graph Drawing 2018

    work page 2018

  28. [28]

    Intersection graphs of segments and $\exists\mathbb{R}$

    Jiˇ r´ ı Matouˇ sek. Intersection graphs of segments and∃R. Arxiv, 1406.2636, 2014. URL: http: //arxiv.org/abs/1406.2636, arXiv:1406.2636

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  29. [29]

    The universality theorems on the classification problem of configuration varieties and convex polytopes varieties

    Nicolai E Mn¨ ev. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Oleg Y. Viro, editor, Topology and geometry – Rohlin seminar , pages 527–543. Springer-Verlag Berlin Heidelberg, 1988

    work page 1988

  30. [30]

    Nemhauser and Zev Ullmann

    George L. Nemhauser and Zev Ullmann. Discrete dynamic programming and capital allocation. Management Science, 15(9):494–505, 1969

    work page 1969

  31. [31]

    Mn¨ ev’s universality theorem revisited.S´ eminaire Lotaringien de Combina- toire, 34, 1995

    J¨ urgen Richter-Gebert. Mn¨ ev’s universality theorem revisited.S´ eminaire Lotaringien de Combina- toire, 34, 1995

    work page 1995

  32. [32]

    J¨ urgen Richter-Gebert and G¨ unter M. Ziegler. Realization spaces of 4-polytopes are universal. Bulletin of the American Mathematical Society , 32(4):403–412, 1995

    work page 1995

  33. [33]

    6: Oriented matroids

    J¨ urgen Richter-Gebert and G¨ unter M Ziegler. 6: Oriented matroids. In Handbook of discrete and computational geometry, pages 159–184. Chapman and Hall/CRC, 2017

    work page 2017

  34. [34]

    Minicourse on smoothed analysis

    Heiko R¨ oglin. Minicourse on smoothed analysis. https://algo.rwth-aachen.de/Lehre/SS07/ VRA/Material/SmoothedAnalysis.pdf, 2007. Online; accessed April 2019

    work page 2007

  35. [35]

    Smoothed Complexity and Pseudopolynomial-Time Algorithms

    Tim Roughgarden. Smoothed Complexity and Pseudopolynomial-Time Algorithms. https: //theory.stanford.edu/~tim/f14/l/l15.pdf, 2014. Online; accessed August 2018

    work page 2014

  36. [36]

    Beyond Worst-Case Analysis

    Tim Roughgarden. Beyond worst-case analysis. Arxiv, 1806.09817, 2018. arXiv:1806.09817

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  37. [37]

    Realizability of graphs and linkages

    Marcus Schaefer. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory, pages 461–482. Springer, 2013

    work page 2013

  38. [38]

    Fixed points, nash equilibria, and the existential the- ory of the reals

    Marcus Schaefer and Daniel Stefankovic. Fixed points, nash equilibria, and the existential the- ory of the reals. Theory Comput. Syst. , 60(2):172–193, 2017. URL: https://doi.org/10.1007/ s00224-015-9662-0 , doi:10.1007/s00224-015-9662-0 . 13

    work page doi:10.1007/s00224-015-9662-0 2017

  39. [39]

    The complexity of tensor rank

    Marcus Schaefer and Daniel Stefankovic. The complexity of tensor rank. Theory Comput. Syst. , 62(5):1161–1174, 2018. URL: https://doi.org/10.1007/s00224-017-9800-y , doi:10.1007/ s00224-017-9800-y

    work page doi:10.1007/s00224-017-9800-y 2018

  40. [40]

    A universality theorem for nonnegative matrix factorizations

    Yaroslav Shitov. A universality theorem for nonnegative matrix factorizations. Arxiv 1606.09068, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  41. [41]

    Stretchability of pseudolines is np-hard

    Peter Shor. Stretchability of pseudolines is np-hard. Applied Geometry and Discrete Mathematics- The Victor Klee Festschrift , 1991

    work page 1991

  42. [42]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) , 51(3):385–463, 2004

    work page 2004

  43. [43]

    Smoothed order types

    Martijn van Schaik. Smoothed order types. Bachelor Thesis, 2019

    work page 2019

  44. [44]

    Oriented matroids today

    G¨ unter M Ziegler. Oriented matroids today. World Wide Web http://www. math. tuberlin. de/˜ ziegler, 1996. 14 g(1) g(2) + g(3) + ... g(b) + . . . g(b) ∑b t=1 g(t) ∑b t=2 g(t) ∑b t=b g(t) g(2) g(3) + g(3) g(b) Figure 6: Rewriting the sums. A Poof of Lemma 5 Lemma 5. Given a function f : Ω→{ 1,...,b } and assume that Pr(f(x)>b ) = 0. Then it holds that E[f...

    work page 1996