Pith. sign in

REVIEW 3 major objections 3 minor 69 references

Optimal Curve Straightening is $\exists\mathbb{R}$-Complete

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that deciding whether a self-intersecting closed curve is isotopic to an m-vertex polygon is ∃R-complete—exactly as hard as the existential theory of the reals.

desk verdict The ∃R-completeness claim is plausible and the hardness side is solid, but the ETR membership formula has a load-bearing disjunction/conjunction error and the universality corollary overstates what is proved. read the letter →

arxiv 1908.09400 v2 pith:PA7SQF5O submitted 2019-08-25 cs.CG

Jeff Erickson This is my paper · ORCID
classification cs.CG MSC 68Q1768U0552C35
keywords curvestraighteningisotopyrealizationspacepseudolinestretchabilityexistentialtheoryofthereals∃R-completepolygoncrossingcodesminimum-segmentdrawings
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes the exact computational complexity of optimal curve straightening: given a generic self-intersecting closed curve and an integer $m$, asking whether some $m$-gon is isotopic to the curve is $\exists\mathbb{R}$-complete. That places the problem on the same footing as deciding whether a system of polynomial equations and inequalities has a real solution, hence NP-hard and contained in PSPACE. The proof has two halves. Hardness comes from wrapping a wiring-diagram pseudoline arrangement with exterior loops so that the resulting curve is isotopic to a $4n$-gon exactly when the arrangement is stretchable. Membership in $\exists\mathbb{R}$ is the delicate half: the paper encodes the curve by signed crossing codes and 'guesses' which polygon edges carry each crossing, then writes an ETR formula of length $O(n^4)$ that is satisfiable exactly when a valid isotopic polygon exists. Universality consequences follow from the same reduction: isotopy realization spaces of polygons can have the homotopy type of any semialgebraic set, and some isotopy classes force every integer-coordinate polygon to have doubly exponential diameter.

What carries the argument

The load-bearing construction is a reduction from pseudoline stretchability. A simple pseudoline arrangement in wiring-diagram form is truncated inside a rectangle, and its $2n$ endpoints are joined outside the rectangle by $n$ disjoint paths, each carrying two outward-facing loops called the fringe. The resulting generic closed curve $\gamma_\Psi$ has exactly $2n$ self-intersections contributed by the fringe; Lemma 3.1 forces any isotopic polygon to have at least $4n$ vertices, and Lemma 3.2 shows a $4n$-gon exists exactly when the pseudoline arrangement is stretchable, by stapling segments onto a line arrangement. For the upper bound, the central encoding objects are the signed crossing code, which records the pairing and crossing directions of the curve's self-intersections, and the edge code, which records which polygon edge contains each crossing. The ETR formula existentially guesses the edge code and expands indexed disjunctions to simulate array indexing by the edge variables, turning the isotopy check into a polynomial-size system of polynomial equalities and inequalities.

What would settle it

Run the paper's construction on the well-known minimal non-stretchable arrangement of nine pseudolines and inspect the isotopy realization space $\Sigma(\gamma_\Psi,36)$. If that space is nonempty, Lemma 3.2 and Theorem 3.3 are false; if it is empty but its homotopy type differs from the pseudoline arrangement's realization space, Theorem 3.4 is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.3 and Corollary 4.2: the decision problem CURVETOPOLYGON is $\exists\mathbb{R}$-complete. For any generic closed curve with $n$ self-crossings, there is a polynomial-time construction of a curve $\gamma_\Psi$ from a pseudoline arrangement $\Psi$ such that $\gamma_\Psi$ is isotopic to a $4n$-gon if and only if $\Psi$ is stretchable (Lemma 3.2); conversely, for any curve $\gamma$ and any $m=O(n)$, there is an ETR sentence of length $\Theta(nm^3)=O(n^4)$ that is true if and only if $\gamma$ is isotopic to a generic $m$-gon (Theorem 4.1). The paper also claims that every semialgebraic set is homotopy equivalent to the isotopy realization space $\Sigma(\gamma,m)$ of some closed curve and some integer $m$ (Theorem 3.4), and that some isotopy classes force any integer-coordinate representative to have diameter $2^{2^{\Omega(m)}}$ (Corollary 3.5).

Load-bearing premise

The universality and bit-precision corollaries assume the reduction preserves the full solution space of the pseudoline arrangement as a topological space, not merely whether that space is empty; the paper states this as a natural corollary but does not prove the required homotopy equivalence.

Editorial extensions

If this is right

  • Optimal curve straightening is NP-hard and lies in PSPACE, so no polynomial-time algorithm exists unless the existential theory of the reals is polynomial-time decidable.
  • The minimum number of vertices in an isotopic polygon is not a purely combinatorial invariant of the curve: deciding it requires solving polynomial equations over the reals.
  • For suitable curves, the space of all isotopic $m$-gons realizes the homotopy type of an arbitrary semialgebraic set, so polygon realization spaces can be disconnected or otherwise topologically complex in ways that mirror real solution sets.
  • Some isotopy classes force every integer-coordinate isotopic polygon to have diameter $2^{2^{\Omega(m)}}$, meaning exponentially many bits per coordinate in the worst case.
  • In contrast, the minimum-bend orthogonal polygon isotopic to a given curve can be computed in $O(n^{4/3}\operatorname{polylog} n)$ time via planar min-cost flow, so the hardness is specific to unrestricted straight-line edges rather than to isotopy verification itself.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the universality claim holds in full, no finite combinatorial certificate can encode all optimal straightenings: the solution space itself can carry the topology of any semialgebraic set, so any complete output specification would have to contain real algebraic data.
  • The membership proof's reliance on guessing an edge code suggests a sharper question: whether the problem remains $\exists\mathbb{R}$-hard for curves whose signed crossing code determines a unique planar embedding, or whether resolving the outer-face ambiguity collapses the problem to NP.
  • The same fringe-and-staples construction may transfer directly to minimum-segment drawings of plane graphs, offering an alternative route to $\exists\mathbb{R}$-hardness that bypasses arrangement-graph recognition.
  • The generic-curve assumption is probably inessential: applying the same encoding machinery to non-generic curves via infinitesimal perturbation would test whether degenerate crossings only make the decision problem easier rather than harder.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the computational complexity of the following decision problem, called CURVETOPOLYGON: given a generic self-intersecting closed curve γ in the plane and an integer m, decide whether there exists an m-vertex polygon isotopic to γ. The authors claim this problem is ∃R-complete. The hardness direction is a polynomial-time reduction from pseudoline stretchability: from a wiring diagram Ψ of n pseudolines they construct a curve γΨ, and they prove that γΨ is isotopic to a 4n-gon if and only if Ψ is stretchable. The membership direction constructs an ETR sentence that existentially quantifies the vertex coordinates of the polygon and an edge code, and then enforces generality, the correct number of crossings, crossing signs, and crossing order along each edge. The paper also claims a universality theorem: every semialgebraic set is homotopy equivalent to the isotopy realization space Σ(γ,m) of some curve and integer m, and an exponential-precision corollary for integer-coordinate isotopic polygons.

Significance. If the proofs are correct, the paper resolves the complexity of optimal curve straightening and adds a natural geometric decision problem to the growing list of ∃R-complete problems. The hardness construction is elegant and appears sound: it reduces from the classical ∃R-complete pseudoline stretchability problem, uses only simple local gadgets, and contains no circularity. The membership approach is also interesting, in particular the use of existentially quantified edge codes to avoid direct indexing into arithmetic expressions. However, the membership proof as printed contains a logical-connective error in the key crossing-order formula, and the universality theorem is asserted without the required homotopy-equivalence argument. These issues affect the central completeness claim and the advertised stronger results, so the paper needs substantial revision before the claims can be accepted as proven.

major comments (3)
  1. [§4.7, CrossingOrder; Theorem 4.1; Corollary 4.2] The displayed formula CrossingOrder(P, twin, edge) ≡ ⋁_{i=1}^{2n−1} OrderedX(i) uses a disjunction, but the surrounding prose requires that the crossings on every edge appear in the correct order, which demands a conjunction over all consecutive crossing indices i. With the printed disjunction, the formula is satisfied as soon as any single i satisfies OrderedX(i); for instance, if the first two crossing indices lie on different edges, OrderedX(1) is true, and the rest of the polygon may have arbitrarily wrong crossing order. This is not a cosmetic issue: Theorem 4.1 and Corollary 4.2 rely on this exact formula to prove the ETR-membership of CURVETOPOLYGON. The confusion is visible in §4.2, where an indexed conjunction is explicitly called an 'indexed disjunction.' The proof can likely be repaired by replacing the outer disjunction with a conjunction, but as written the membership argument does not go through.
  2. [§3, Theorem 3.4 and Corollary 3.5] Theorem 3.4 is asserted as a 'natural corollary' of Mnëv's universality theorem, but the paper never defines a map between the isotopy realization space Σ(γΨ, 4n) and the realization space of the pseudoline arrangement Ψ, nor proves that such a map is a homotopy equivalence. The hardness reduction shows only that one space is nonempty if and only if the other is nonempty; it does not establish that the spaces have the same homotopy type. In particular, the exterior fringe loops and the stapling construction could a priori introduce additional degrees of freedom or collapse components. Without a proof of homotopy equivalence, Theorem 3.4 and the exponential-precision corollary Corollary 3.5 are unsupported. This issue does not affect the ∃R-hardness of the decision problem, but it does affect a central advertised contribution.
  3. [§4.3, GoodPolygon] The text states that 'p1 is the rightmost vertex of P,' but the formula GoodPolygon(P) includes the conjunct ⋀_{i=2}^m (x1 ≤ xi), which forces x1 to be the minimum, i.e., the leftmost vertex, not the rightmost. Since the signed crossing code is defined relative to a chosen basepoint on the outer face, this inconsistency must be resolved: either change the formula to x1 ≥ xi or change the prose to say 'leftmost.' The intended inequality is clear, but as printed the formula contradicts the explanation of the basepoint convention.
minor comments (3)
  1. [§3, Lemma 3.2, staple construction] In the paragraph describing the construction of PL, the text says 'we connect the left endpoints p_{2i−1} and pi' and 'the right endpoints q_{2i} and q_{2i+1}' with vertical staples; the first phrase should presumably read 'p_{2i−1} and p_{2i}' to match the parity pattern of the wiring-diagram connections. Please correct this indexing typo.
  2. [Abstract] The abstract contains the duplicated word 'implies implies' in 'Our reduction implies implies two stronger results'; this should be corrected.
  3. [§4.2] The sentence 'the indexed disjunction ⋀_{i=1}^{2n−1} (edge_i ≤ edge_{i+1}) is notational shorthand for the explicit disjunction (edge_1 ≤ edge_2) ∧ ...' misuses the word 'disjunction' for a conjunction. Given that the same symbol/terminology confusion appears in the load-bearing formula of §4.7, the notation should be made consistent and carefully checked throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the ∃R-completeness proof reduces to external pseudoline-stretchability and ETR results, with no fitted parameter or self-citation carrying the derivation.

full rationale

I traced the two derivation chains in the paper. The hardness direction (Section 3, Lemmas 3.1 and 3.2) reduces pseudoline stretchability to CURVETOPOLYGON by constructing a curve γΨ whose 4n-gon isotopy forces a line arrangement isomorphic to Ψ; the converse constructs an isotopic 4n-gon from any stretching of Ψ. This uses Mnëv's ∃R-completeness theorem [47,48] as an external input, and the lemma's proof does not assume the target result. The membership direction (Section 4) translates the isotopy condition into an ETR sentence ISOTOPIC TOPOLYGON(γ,m) with existentially quantified polygon coordinates and guessed edge codes; all predicates (GoodPolygon, NumCrossings, WellFormed, CrossingSigns, CrossingOrder) are defined directly from the input curve's crossing code, and no fitted data or target-derived constant is renamed as a prediction. The universal-precision and homotopy corollaries invoke Mnëv's universality theorem and Goodman–Pollack–Sturmfels spread results as independent external theorems. I found no self-citation that is load-bearing; the reference list contains no paper by the author. The passages that deserve flagging are correctness risks rather than circularity: Section 4.7 writes 'CrossingOrder(P, twin, edge) ≡ ⋁_{i=1}^{2n−1} OrderedX(i)' as a disjunction where the intended consecutive-pair condition would require a conjunction, and Theorem 3.4 is asserted 'as a natural corollary of Mnëv's universality theorem' without proving the needed homotopy equivalence between Σ(γ,m) and the pseudoline realization space. Neither of these gaps makes a claimed result equivalent to its input by construction, so they do not raise the circularity score. The central claim is self-contained against external benchmarks, and the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof rests on standard results in real complexity and on Carter's classification of immersed curves. No free parameters are fitted. The only ad hoc assumption is the unproved homotopy preservation needed for the universality corollaries.

assumptions (4)
  • standard math Mnëv's universality theorem: for any semialgebraic set V, there is a pseudoline arrangement whose realization space is homotopy equivalent to V.
    Used as the external hard problem and as the basis for Theorem 3.4.
  • standard math Pseudoline stretchability is ∃R-complete (Mnëv, Shor, Richter-Gebert).
    Basis for the hardness reduction in Section 3.
  • domain assumption A signed crossing code of a generic curve determines its embedding on the sphere, and fixing the outer face determines the plane embedding (Carter [19]).
    Used in Section 4 to justify checking only twin, sign, and edge code.
  • ad hoc to paper The reduction from pseudoline arrangements to curves preserves the realization space up to homotopy equivalence.
    Needed for Theorem 3.4 and Corollary 3.5; asserted without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Curve Straightening is $\exists\mathbb{R}$-Complete." pith.science (2026). https://pith.science/paper/PA7SQF5O

@misc{pith2026190809400,
  author       = {Pith},
  title        = {Pith review of: Optimal Curve Straightening is $\exists\mathbbR$-Complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PA7SQF5O}},
  note         = {Machine review of 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 $\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. First, there are isotopy classes in which every $m$-gon with integer coordinates requires $2^{\Omega(m)}$ bits of precision. Second, for any semi-algebraic set $V$, there is an integer $m$ and a closed curve $\gamma$ such that the space of all $m$-gons isotopic to $\gamma$ is homotopy equivalent to $V$.

Figures

Figures reproduced from arXiv: 1908.09400 by the authors.

Figure 1
Figure 1. Two polygons isotopic to the same closed curve. This quadratic gap between best and worst cases motivates the following question: How quickly can we find a polygon with the minimum number of vertices that is isotopic to a given closed curve? This is a special case of minimum-segment drawings problem proposed by Dujmovi´c et al. [26], which asks for 1 arXiv:1908.09400v2 [cs.CG] 27 Aug 2019 [PITH_FULL_IMAGE:figures/f… view at source ↗
Figure 2
Figure 2. (a) Ringel’s [56] minimal non-stretchable arrangement of 9 pseudolines. (b) A closed curve derived from Ringel’s arrangement that is not isotopic to any 36-gon. Together with Mnëv’s universality theorem for pseudoline arrangements [47, 48], our reduction implies a similar universality result for polygons: the set of all polygons isotopic to a given curve and with a given number of vertices can have essentially arbit… view at source ↗
Figure 3
Figure 3. A “wiring diagram” pseudoline arrangement. To avoid parity issues, we also assume without loss of generality that n is odd. Otherwise, consider the set Ψ 0 = Ψ ∪ {ψ0 }, where ψ0 is a new “wire” that passes above all n 2  intersection points of Ψ and 3Mnëv’s universality theorem also implies several other universality results in algebraic geometry, collectively dubbed “Murphy’s Law” by Vakim [43,67] [PITH_FULL_IMAG… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: The closed curve γΨ derived from the pseudoline arrangement Ψ in [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Polygonalizing a simple loop requires at least two vertices It follows immediately that P contains at least two vertices for each of the 2n loops in the fringe of γΨ, and thus at least 4n vertices in total. ƒ Lemma 3.2. Let Ψ be any set of n pseudolines, for any odd in…
Figure 6
Figure 6. Figure 6: Stapling a line arrangement into a polygon; compare with [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: A closed curve with exactly three valid signed crossing codes; compare with [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: shows a generic polygon P whose convex hull has four vertices; along with the signed crossing and edge codes that result from choosing each convex hull vertex as the basepoint. Each signed crossing code is also a valid signed crossing code for the curve γ in [PITH_FUL…
Figure 9
Figure 9. Figure 9: Le : cross+ (i, j) = cross− (j, i). Right: cross− (i, j) = cross+ (j, i) At this point we would like to define CrossingSigns(P,twin,sign, edge) ≡ ^ 2n i=1  [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: OrderedP(i, j, k) We need to express this relation in terms of crossing indices, instead of edge indices. The following expression states that the ith and (i +1)st crossings are correctly ordered, unless they appear on different edges. OrderedX(i) ≡ (edgei 6= edgei+1 …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 64 canonical work pages

  1. [1]

    The art gallery problem is ∃R- complete

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃R- complete. Proc. 50th Ann. ACM Symp. Theory Comput. , 65–73, 2018. arXiv:1704.06969

    arXiv 2018

  2. [2]

    Adiprasito, Arnau Padrol, and Louis Theran

    Karim A. Adiprasito, Arnau Padrol, and Louis Theran. Universality theorems for inscribed polytopes and Delaunay triangulations. Discrete Comput. Geom. 54(2):412–431, 2015. arXiv:406.7831

    work page 2015

  3. [3]

    Felzenszwalb, Ross B

    Ronen Basri, Pedro F . Felzenszwalb, Ross B. Girshick, David W . Jacobs, and Caroline J. Klivans. Visibility constraints on features of 3D objects. Proc. 2009 IEEE Conf. Comput. Vision Pattern Recog. , 1231–1238, 209

    work page 2009

  4. [4]

    Algorithms in Real Algebraic Geometry , 2nd edition

    Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry , 2nd edition. Algorithms and Computation in Mathematics 10. Springer-Verlag, 2006

    work page 2006

  5. [5]

    The complexity of computing the minimum rank of a sign pattern matrix

    Amey Bhangale and Swastik Kopparty . The complexity of computing the minimum rank of a sign pattern matrix. Preprint, May 2015. arXiv:1503.04486v2

    arXiv 2015

  6. [6]

    Some provably hard crossing number problems.Discrete Comput

    Daniel Bienstock. Some provably hard crossing number problems.Discrete Comput. Geom. 6(3):443– 459, 1991

    work page 1991

  7. [7]

    A catalog of∃R-complete decision problems about Nash equilibria in multi-player games

    Vittorio Bilò and Marios Mavronicolas. A catalog of∃R-complete decision problems about Nash equilibria in multi-player games. Proc. 33rd Symp. Theor . Aspects Comput. Sci., 17:1–17:13, 2016. Leibniz Int. Proc. Informatics 47, Schloss Dagstuhl–Leibniz-Zentrum für Informatik

    work page 2016

  8. [8]

    ∃R-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

    Vittorio Bilò and Marios Mavronicolas. ∃R-complete decision problems about symmetric Nash equilibria in symmetric multi-player games. Proc. 34rd Symp. Theor . Aspects Comput. Sci., 13:1– 13:14, 2017. Leibniz Int. Proc. Informatics 66, Schloss Dagstuhl–Leibniz-Zentrum für Informatik

    work page 2017

Show all 69 references
  1. [9]

    Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. Oriented Matroids, second edition. Encyclopedia of Mathematics and its Applications 46. Cambridge Univ. Press, 2000

    2000

  2. [10]

    Complexity and Real Computation

    Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation . Springer, 1998

    1998

  3. [11]

    Computational Synthetic Geometry

    Jürgen Bokowski and Bernd Sturmfels. Computational Synthetic Geometry . Lecture Notes Math

  4. [12]

    Properties of arrangement graphs

    Prosenjit Bose, Hazel Everett, and Stephen Wismath. Properties of arrangement graphs. Int. J. Comput. Geom. Appl. 13(6):447–462, 2003

    2003

  5. [13]

    Counting complexity classes for numeric computations ii: Algebraic and semialgebraic sets

    Peter Bürgisser and Felipe Cucker. Counting complexity classes for numeric computations ii: Algebraic and semialgebraic sets. J. Complexity 22(2):147–191, 2006

    2006

  6. [14]

    Some algebraic and geometric computations in PSPACE.Proc

    John Canny . Some algebraic and geometric computations in PSPACE.Proc. 20th ACM Sympos. Theory. Comput., 460–467, 1988.〈https://www2.eecs.berkeley .edu/Pubs/TechRpts/1988/6041.html〉

    1988

  7. [15]

    Computational geometry column 62

    Jean Cardinal. Computational geometry column 62. SIGACT News 46(4):69–78, 2015

    2015

  8. [16]

    Inter- section graphs of rays and grounded segments

    Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. Inter- section graphs of rays and grounded segments. J. Graph Algorithms Appl. 22(2):273–295, 2018. arXiv:1612.03638. Jeff Erickson 15

    2018 arXiv

  9. [17]

    Recognition and complexity of point visibility graphs

    Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. Discrete Comput. Geom. 57(1):164–178, 2017. arXiv:1503.07082

    2017 arXiv

  10. [18]

    The complexity of simultaneous geometric graph embedding

    Jean Cardinal and Vincent Kusters. The complexity of simultaneous geometric graph embedding. J. Graph Algorithms Appl. 19(1):259–272, 2015. arXiv:1302.7127

    2015 arXiv

  11. [19]

    Scott Carter

    J. Scott Carter. Classifying immersed curves. Proc. Amer . Math. Soc. 111(1):281–287, 1991

    1991

  12. [20]

    The complexity of drawing graphs on few lines and few planes

    Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky , Oleg Verbitsky , and Alexander Wolff. The complexity of drawing graphs on few lines and few planes. Proc. 15th Algorithms Data Struct. Symp. (WADS) , 265–276, 2017. Lecture Notes Comput. Sci. 10389, Springer-V...

    2017 arXiv

  13. [21]

    Algorithmic graph embeddings

    Jianer Chen. Algorithmic graph embeddings. Theoret. Comput. Sci. 161(2):247–266, 1997

    1997

  14. [22]

    Cohen and Uriel G

    Joel E. Cohen and Uriel G. Rothblum. Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Alg. Appl. 190:149–168, 1993

    1993

  15. [23]

    Accelerated bend minimization

    Sabine Cornelson and Andreas Karrenbauer. Accelerated bend minimization. J. Graph Algorithms Appl. 16(3):635–650, 2012

    2012

  16. [24]

    Dobbins, Andreas Holmsen, and Tillman Miltzow

    Michael G. Dobbins, Andreas Holmsen, and Tillman Miltzow. A universality theorem for nested polytopes. Preprint, August 2019. arXiv:1908.02213

    2019 arXiv

  17. [25]

    Dowker and Morwen B

    Clifford H. Dowker and Morwen B. Thistlethwaite. Classification of knot projections. T opology Appl. 16(1):19–31, 1983

    1983

  18. [26]

    Vida Dujmovi´c, David Eppstein, Matthew Suderman, and David R. Wood. Drawings of pla- nar graphs with few slopes and segments. Comput. Geom. Theory Appl. 38(3):194–212, 2007. arXiv:math.CO/0606450

    2007

  19. [27]

    A note on minimum-segment drawings of planar graphs

    Stephane Durocher, Debajyoti Mondal, Rahnuma Islam Nishat, and Sue Whitesides. A note on minimum-segment drawings of planar graphs. J. Graph Algorithms Appl. 17(3):301–328, 2013

    2013

  20. [28]

    Stefan Felsner and Jacob E. Goodman. Psuedoline arrangements. CRC Handbook of Discrete and Computational Geometry, chapter 5, 125–157, 2017. CRC Press.〈https://www.csun.edu/~ctoth / Handbook/HDCG3.html〉

    2017

  21. [29]

    Vazirani, and Sadra Yazdanbod.∃R-completness for decision version of multi-player (symmetric) Nash equilibria

    Jugal Garg, Ruta Mehta, Vijay V . Vazirani, and Sadra Yazdanbod.∃R-completness for decision version of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput. 6(1):1:1–1:23, 2018

    2018

  22. [30]

    Nachlass

    Carl Friedrich Gauß. Nachlass. I. Zur Geometria situs. Werke, vol. 8, 271–281, 1900. Teubner. Originally written between 1823 and 1840

    1900

  23. [31]

    Nachlass

    Carl Friedrich Gauß. Nachlass. II. Zur Geometrie der Lage, für zwei Raumdimensionen. Werke, vol. 8, 282–285, 1900. Teubner

    1900

  24. [32]

    Jacob E. Goodman. Proof of a conjecture of Burr, Grünbaum, and Sloane. Discrete Math. 32:27–35, 1980

    1980

  25. [33]

    Goodman and Richard Pollack

    Jacob E. Goodman and Richard Pollack. Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines. J. Comb. Theory Ser . A 29(3):385–390, 1980. 16 Optimally Curve Straightening is ∃R-Complete

    1980

  26. [34]

    Goodman, Richard Pollack, and Bernd Sturmfels

    Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. Coordinate representation of order types requires exponential storage. Proc. 21st Ann. ACM Symp. Theory Comput. , 405–410, 1989

    1989

  27. [35]

    Goodman, Richard Pollack, and Bernd Sturmfels

    Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. The intrinsic spread of a configuration in Rd. J. Amer . Math. Soc. 3(3):639–651, 1990

    1990

  28. [36]

    Arrangements and Spreads

    Branko Grünbaum. Arrangements and Spreads. Regional Conf. Ser. Math. 10. American Mathematical Society , 1972

    1972

  29. [37]

    Guibas and Jorge Stolfi

    Leonidas J. Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graphics 4(2):75–123, 1985

    1985

  30. [38]

    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 complete for real nondeterministic polytime Blum-Shub-Smale machines. Proc. 6th Conf. Mach. Comput. Universality, 85–92, 2013. Electron. Proc. Theoret. Comput. Sci. 128. arXiv:1309.1270

    2013 arXiv

  31. [39]

    On the complexity of the planar slope number problem

    Udo Hoffmann. On the complexity of the planar slope number problem. J. Graph Algorithms Appl. 21(2):183–193, 2017

    2017

  32. [40]

    Michael Kapovich and John J. Millson. Universality theorems for configuration spaces of planar linkages. T opology41(6):1051–107, 2002

    2002

  33. [41]

    Min-cost flow in unit-capacity planar graphs

    Adam Karczmarz and Piotr Sankowski. Min-cost flow in unit-capacity planar graphs. Preprint, July

  34. [42]

    Intersection graphs of segments.J

    Jan Kratochvíl and Jiˇrí Matoušek. Intersection graphs of segments.J. Comb. Theory Ser . B62(2):289– 315, 1994

    1994

  35. [43]

    Mnëv-Sturmfels universality for schemes

    Seok Heyong Lee and Ravi Vakil. Mnëv-Sturmfels universality for schemes. A Celebration of Algebraic Geometry, 457–468, 2013. Clay Math. Proc. 18, Amer. Math. Soc. arXiv:1202.3934

    2013 arXiv

  36. [44]

    Die teilung der projektiven ebene durch gerade und pseudogerade

    Friedrich Levi. Die teilung der projektiven ebene durch gerade und pseudogerade. Ber . Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 78:256–267, 1926

    1926

  37. [45]

    Intersection graphs of segments and∃R

    Jiˇrí Matoušek. Intersection graphs of segments and∃R. Preprint, June 2014. arXiv:1406.2636

    2014 arXiv

  38. [46]

    Integer realizations of disk and segment graphs

    Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. J. Comb. Theory Ser . B103(1):114–143, 2013. arXiv:1111.2931

    2013 arXiv

  39. [47]

    Nikolai E. Mnëv. Varieties of combinatorial types of projective configurations and convex polyhedra. Dokl. Akad. Nauk SSSR 283(6):1312–1314, 1985. in Russian

    1985

  40. [48]

    Nikolai E. Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. T opology and geometry—Rohlin Seminar , 527–543, 1988. Lecture Notes Math. 1346, Springer

    1988

  41. [49]

    Muller and Franco P

    David E. Muller and Franco P . Preparata. Finding the intersection of two convex polyhedra.Theoret. Comput. Sci. 7:217–236, 1978

    1978

  42. [50]

    Delaunay triangulations with disconnected realization spaces

    Arnau Padrol and Louis Theran. Delaunay triangulations with disconnected realization spaces. Proc. 30th Ann. Symp. Comput. Geom. , 163–170, 2014

    2014

  43. [51]

    Recognising multidimensional euclidean preferences

    Dominik Peters. Recognising multidimensional euclidean preferences. Proc. 31st AAAI Conf. Artif. Intell., 642–648, 2017.〈https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14947〉. Jeff Erickson 17

    2017

  44. [52]

    On the computational complexity and geometry of the first-order theory of the reals, Part I

    James Renegar. On the computational complexity and geometry of the first-order theory of the reals, Part I. J. Symb. Comput. 13(3):255–299, 1992

    1992

  45. [53]

    Mnëv’s universality theorem revisited

    Jürgen Richter-Gebert. Mnëv’s universality theorem revisited. Séminaire Lotharingien de Combina- toire B34h:15 pp., 1995.〈https://www.mat.univie.ac.at/~slc /wpapers/s34berlin.html〉

    1995

  46. [54]

    Realization spaces of polytopes

    Jürgen Richter-Gebert. Realization spaces of polytopes . Lecture Notes Math. 1643. Springer, 1996

    1996

  47. [55]

    Kombinatorische Realisierbarkeitskriterien für orientierte Matroide

    Jürgen Richter. Kombinatorische Realisierbarkeitskriterien für orientierte Matroide. Mitt. Math. Sem. Gießen 194:1–112, 1989

    1989

  48. [56]

    Teilungen der Ebene durch Geraden oder topologische Geraden.Math

    Gerhard Ringel. Teilungen der Ebene durch Geraden oder topologische Geraden.Math. Z. 64(1):79– 102, 1956

    1956

  49. [57]

    Complexity of some geometric and topological problems

    Marcus Schaefer. Complexity of some geometric and topological problems. Proc. 17th Int. Symp. Graph Drawing, 334–344, 2009. Lecture Notes Comput. Sci. 5849, Springer

    2009

  50. [58]

    Realizability of graphs and linkages

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

    2013

  51. [59]

    Fixed points, Nash equilibria, and the existential theory of the reals

    Marcus Schaefer and Daniel Štefankoviˇc. Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Systems 60(2):172–193, 2017

    2017

  52. [60]

    The complexity of tensor rank

    Marcus Schaefer and Daniel Štefankoviˇc. The complexity of tensor rank. Theory Comput. Systems 62(5):1161–1174, 2018. arXiv:1612.04338

    2018 arXiv

  53. [61]

    The nonnegative rank of a matrix: Hard problems, easy solutions

    Yaroslav Shitov. The nonnegative rank of a matrix: Hard problems, easy solutions. SIAM Review 59(4):794–800, 2017. arXiv:1605.04000

    2017 arXiv

  54. [62]

    Peter W . Shor. Stretchability of pseudolines is NP-hard.Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift , 531–554, 1991. DIMACS Series Discrete Math. Theor. Comput. Sci. 4, Amer. Math. Soc. and Assoc. Comput. Mach

    1991

  55. [63]

    Geometrie der Lage

    Karl Georg Christian von Staudt. Geometrie der Lage . Verlag von Bauer and Rapse (Julius Merz), Nürnberg, 1847

  56. [64]

    On knots I

    Peter Guthrie Tait. On knots I. Trans. Royal Soc. Edinburgh 28(1):145–190, 1876–7. 〈https: //babel.hathitrust.org/cgi/pt?id=njp.32101074834365&seq=199〉

  57. [65]

    On embedding a graph in the grid with the minimum numberof bends

    Roberto Tamassia. On embedding a graph in the grid with the minimum numberof bends. SIAM J. Comput. 16(3):421–444, 1987

    1987

  58. [66]

    William T . Tutte. A census of planar maps.Canad. J. Math. 15:249–271, 1963

    1963

  59. [67]

    Murphy’s law in algebraic geometry: Badly-behaved deformation spaces

    Ravi Vakil. Murphy’s law in algebraic geometry: Badly-behaved deformation spaces. Invent. Math. 164(3):569–590, 2006. arXiv:math.AG/0411469

    2006

  60. [68]

    Edge-based data structures for solid modeling in curved-surface environments

    Kevin Weiler. Edge-based data structures for solid modeling in curved-surface environments. IEEE Comput. Graph. Appl. 5(1):21–40, 1985

    1985

  61. [1355]

    Springer-Verlag, 1989

    1989

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.