Pith. sign in

REVIEW 1 major objections 4 minor 22 references

Minimal Representations of Order Types by Geometric Graphs

T0 review · 1 major / 4 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 exit graph of any planar point set—the edges that block order-type changes—is a sparse supporting graph whose edges are fully characterized in the dual line arrangement.

desk verdict A genuinely new concept with a clean supporting-graph theorem and a solid dual characterization; the lower-bound proof has one under-derived step that needs fixing before acceptance. read the letter →

arxiv 1908.05124 v2 pith:VAGFBGE5 submitted 2019-08-14 math.CO cs.CG

Oswin Aichholzer , Martin Balko , Michael Hoffmann , Jan Kynčl , Wolfgang Mulzer , Irene Parada , Alexander Pilz , Manfred Scheucher
show 3 more authors
Pavel Valtr Birgit Vogtenhuber Emo Welzl
This is my paper · ORCID
classification math.COcs.CG MSC 52C3052C4505C62
keywords exitedgesordertypessupportinggraphsgeometricpseudolinearrangementstriangularcellspoint-linedualitycontinuousmotion
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

The paper introduces exit edges as a way to draw an order type—the complete record of which triples of points are oriented clockwise or counterclockwise—with far fewer segments than the complete graph. An edge $ab$ is an exit edge with witness $c$ when no other point separates $b$ from $c$ by a line through $a$, or $a$ from $c$ by a line through $b$; the paper proves that if a continuous motion of the point set keeps all exit edges straight and never creates two collinear triples at once, the order type cannot change. This makes the exit graph a supporting graph, a compact certificate for the order type that can be recognized unambiguously from the drawing. The paper also gives a dual description of exit edges as empty triangular cells in a line arrangement, which yields an $O(n^2)$-time computation, bounds of $(3n-7)/5$ to $n(n-1)/3$ on their number, and a random construction with $\Theta(n^2)$ exit edges.

What carries the argument

The central object is the exit edge, defined by an empty double-wedge condition: segment $ab$ is an exit edge with witness $c$ exactly when the two wedges spanned by the rays from $a$ toward $b$ and $c$ and from $b$ toward $a$ and $c$ contain no point of $S$. In the dual projective arrangement of lines, an exit edge corresponds to a triangular cell that is not the marked cell $c_{\infty}$, with the witness line determined by the consistent orientation of the cell's boundary and the dual of $ab$ at the cell's exit vertex. This correspondence is the load-bearing bridge: it turns a geometric statement about separating lines into a purely combinatorial statement about triangular cells, which is what allows $O(n^2)$ enumeration and the lower bound arguments based on pseudoline arrangements. A secondary mechanism is the hourglass—a pair of triangular cells sharing an exit vertex—which accounts for exit edges with two witnesses and drives the counting in Proposition 3.

What would settle it

Take any small point set and attempt to morph its exit graph while keeping all exit edges straight and at most one collinearity at a time; if any such motion changes the orientation of a triple, the claim that exit graphs are supporting is false. For the lower-bound proof specifically, construct a simple projective pseudoline arrangement in which two pseudolines bound a halfplane with no other crossings while the special cell is bounded by more than four pseudolines; if such an arrangement exists, the $(3n-7)/5$ bound would require a new argument.

Watch

Extended reading notes

Core claim

For any finite point set $S$ in general position, the exit graph—the geometric graph whose edges are exactly the exit edges—is supporting: every ambient isotopy of the plane that keeps these edges straight and produces at most one collinear triple at any time preserves the order type of $S$. The key mechanism is Proposition 2: if the first collinearity to appear is point $c$ on segment $ab$, then $ab$ must have been an exit edge of the initial set with witness $c$. Thus the exit graph contains an edge for every possible first crossing, so no crossing that changes a triple orientation can occur without breaking an exit edge. In the dual projective line arrangement, an exit edge with witness $c$ is exactly an unmarked triangular cell whose exit vertex is the intersection of the duals of $a$ and $b$ and whose witness line is $c^*$; this characterization makes the concept computable and connects the counting problem to triangular cells in line and pseudoline arrangements.

Load-bearing premise

The linear lower bound depends on the unproved geometric assertion that when two pseudolines enclose a region with no other crossings inside, the arrangement's special cell is bounded by at most four pseudolines, two of them being those; the paper supports this with a figure and a short heuristic, not a full derivation.

Editorial extensions

If this is right

  • Every $n$-point set admits a supporting graph with at most $n(n-1)/3$ edges, and every such set has at least $(3n-7)/5$ exit edges, so compared with the complete graph this saves at least a third of the edges in the worst case.
  • Exit edges can be computed in $O(n^2)$ time and space, making the representation practical for moderate $n$.
  • If the first collinearity in any allowable motion is a point crossing a segment, that segment is necessarily an exit edge; hence the exit graph contains the complete list of possible first crossings.
  • The number of exit edges can be quadratic in expectation for random points, so typical point sets need dense certificates even though worst-case examples use only $n-3$ edges.
  • Every supporting graph on $n \ge 9$ points must contain a crossing; plane graphs cannot serve as sparse order-type certificates.
  • Exit graphs are not always minimal supporting graphs, because the straight-edge requirement combined with non-stretchable pseudoline arrangements can force exit edges that a purely topological supporting graph would not need.

Reading between the lines

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

  • Knowing all exit edges and their witnesses is not enough to recover the order type: the paper's concluding counterexample shows two different order types sharing the same triangular cells and even the same order of cells along each pseudoline. A natural testable extension is to determine what additional data—such as the cyclic order of exit vertices around each witness line—would close this gap.
  • The lower-bound proof's weakest step is the case-(iii) claim that the marked cell is bounded by at most four pseudolines. A computational search over simple pseudoline arrangements for a counterexample to that local claim, or a full proof, would settle whether $(3n-7)/5$ is the right rate or whether the true minimum is lower.
  • Because exit graphs are not always minimal supporting graphs, a next step is to study the minimal supporting graph as an optimization problem; the gap between the exit-graph bound and the $n-3$ construction suggests the true extremal number may be pinned down by stretchability constraints rather than by pure motion arguments.
  • The random-point construction transfers directly to line arrangements: random slopes produce $\Theta(n^2)$ triangular cells, so examples with quadratic exit edges are abundant and not pathological.
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

1 major / 4 minor

Summary. The paper introduces the concept of exit edges for a point set S: an edge ab is an exit edge with witness c if no other point p has the property that the line ap separates b from c or the line bp separates a from c. The exit graph, consisting of all exit edges, is shown to be supporting for S, meaning every continuous motion of the vertices that keeps the exit edges straight and passes through at most one collinearity at a time preserves the order type (Proposition 2 and Corollary 1). The paper gives a dual characterization of exit edges as empty triangular cells in the dual line arrangement (Theorem 1), yielding an O(n^2) enumeration algorithm. The main quantitative result is a lower bound of (3n−7)/5 exit edges for every n≥4 (Proposition 3), together with an upper bound of n(n−1)/3 and a random construction with Θ(n^2) expected exit edges. It also proves structural facts: every supporting graph on at least 9 vertices has a crossing, and unbounded-face vertices of exit graphs are extremal. The paper closes with a conjecture that exit graphs encode the order type and a counterexample showing that triangular cells with their orientations do not suffice.

Significance. The paper is a valuable contribution to the compact representation of order types. The definition of exit edges is natural, and the proof that exit graphs are supporting is clean and well grounded. The dual characterization via empty triangular cells is elegant, enables O(n^2) computation, and connects the problem to pseudoline arrangements. If the lower-bound proof is completed, the paper establishes a linear lower bound (3n−7)/5 and an upper bound n(n−1)/3, showing that exit graphs save a constant fraction of the edges of the complete geometric graph. The random construction with Θ(n^2) exit edges and the structural results on supporting graphs add further interest. The main weakness is the proof of Proposition 3, where a key geometric claim about the marked cell is asserted without a full derivation.

major comments (1)
  1. [Section 4, Proposition 3, case (iii)] The argument bounding the number of case-(iii) pseudolines by four is incomplete. The proof states: 'Since H1 contains no crossing in its interior, it is divided by the other pseudolines into 4-gons and the two triangular cells of the hourglass. In particular, the marked cell is bounded by at most four pseudolines, two of them being l_i and l_j.' The 'in particular' does not follow from the absence of crossings in H1 alone. The empty halfplane H1 does not, by itself, identify a unique cell as the marked cell; for instance, in a four-line arrangement with l_i: y=0, l_j: x=0, c: x+y=1, d: x+y=-1, the halfplane xy>0 contains the hourglass and no crossing in its interior, while the arrangement has cells outside H1 whose boundaries are not forced to include both l_i and l_j. What selects the marked cell must be the exit-vertex orientation introduced in Section 3, but no such argument appears. Because the inequality sum x_i ≥ 3(n−4)+4·(5/2) depends on there being at most four pseudolines in case (iii), the lower bound (3n−7)/5 in Proposition 3 is not established by the current text. A full derivation of the marked-cell claim, or a different argument limiting the number of case-(iii) pseudolines, is required.
minor comments (4)
  1. [Section 4, Theorem 2] In the proof of Theorem 2, the probability that a point p_d lies in the relevant wedge is stated as at most 5/n, but the y-coordinates are uniform on an interval of length n−1, so the natural bound is 5/(n−1); the subsequent use of 10/n is acceptable up to a constant factor but should be adjusted for formal correctness.
  2. [Section 4, Proposition 3, case (iii)] At the end of case (iii), the sentence 'this case can happen for at most two pairs of pseudolines' is confusing; the preceding text concludes that there are at most four pseudolines, and the relationship between pseudolines and pairs should be stated explicitly.
  3. [Section 5, Theorem 3] The proof of Theorem 3 would benefit from a short explanation of why perturbing the collinear points obtained from Dujmović's theorem to the two sides of the line yields two plane straight-line embeddings of the same abstract graph with different order types while preserving planarity.
  4. [Abstract] The phrase 'at least one vertex needs to move across an exit edge' is a slight simplification; the precise statement is that every order-type-changing motion keeps some exit edge straight and moves a witness across it, and this could be clarified in the abstract.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: exit edges are defined independently, all bounds derive from external Grünbaum/Levi/Roudneff results, and the main supporting-graph claim follows from Proposition 2 rather than from an assumed conclusion.

full rationale

The paper's central definition of an exit edge (Definition 2) is given by the absence of separating lines through a or b, independently of the supporting-graph property. Proposition 2 then derives, rather than assumes, that a first collinearity across a segment ab forces ab to be an exit edge, and Corollary 1 follows from that derivation together with Definition 1. The dual characterization (Theorem 1) is a direct consequence of projective duality and the chosen orientation of the marked cell, not a renaming of the target statement: it translates an incidence and emptiness condition into a triangular-cell condition, and the exit-vertex claim is argued from the orientation procedure. The lower bound in Proposition 3 uses external lemmas attributed to Grünbaum and sums incidence counts; no fitted parameter or previously asserted bound is recycled as a prediction. The upper bound and quadratic construction rely on external results (Levi, Roudneff, Harborth, Felsner and Weil) or on an independent probabilistic argument (Theorem 2). The only self-citation is the order type database [1], used for a finite computational check for n = 9 and 10; it is not load-bearing for the main theorems and is externally checkable. The disputed geometric claim in Proposition 3, case (iii), that the marked cell is bounded by at most four pseudolines, is a possible proof gap concerning correctness, but it is not circular: the claim does not rest on the theorem being proved or on a self-citation, so it does not raise the circularity score.

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

The central results rely on standard projective duality and two cited theorems of Grünbaum on pseudoline arrangements; no parameters are fitted and no ad hoc objects are introduced. The new concept 'exit edge' is defined explicitly and does not function as an unexplained explanatory entity.

assumptions (3)
  • standard math Lemma 1 (Grünbaum): every pseudoline in a simple arrangement is incident to at least three triangular cells.
    Used in cases (i) and (ii) of Proposition 3 to lower bound the number of triangular cells incident to each pseudoline.
  • standard math Lemma 2 (Grünbaum): if two pseudolines cross inside a halfplane H bounded by two pseudolines l1, l2, then there is a triangular cell in H incident to l1 but not to l2.
    Used in case (ii) of Proposition 3 to ensure that a pseudoline slicing an hourglass also has two additional triangular cells.
  • standard math Standard projective duality between point sets in the plane and line arrangements, preserving incidences and cell structures.
    Central to Theorem 1 and the O(n²) enumeration algorithm for exit edges.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimal Representations of Order Types by Geometric Graphs." pith.science (2026). https://pith.science/paper/VAGFBGE5

@misc{pith2026190805124,
  author       = {Pith},
  title        = {Pith review of: Minimal Representations of Order Types by Geometric Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VAGFBGE5}},
  note         = {Machine review of arXiv:1908.05124}
}
read the original abstract

In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order type of S. We introduce the concept of exit edges, which prevent the order type from changing under continuous motion of vertices. That is, in the geometric graph on S whose edges are the exit edges, in order to change the order type of S, at least one vertex needs to move across an exit edge. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number.

Figures

Figures reproduced from arXiv: 1908.05124 by the authors.

Figure 1
Figure 1. Representatives of the three order types of five points and the sixteen [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Three different representations of an order type of six points. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The geometric graph on the left can be transformed by an ambient [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: Characterizing exit edges. Left: If the gray region is empty of points, [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Left: moving c over ab to orient (a, b, c) clockwise, without changing the orientation of other triples, would contradict Pappus’s theorem [20]. Right: it is not always possible to move a witness c continuously to the corresponding exit edge ab. deformation as the one …
Figure 6
Figure 6. Figure 6: An illustration of the proof of Theorem 1. If [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Left: the two triangular cells 41 and 42 do not form an hourglass, because they share a vertex that is not an exit vertex. Right: the two triangular cells 41 and 42 form an hourglass because they share an exit vertex [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: In case (iii), both `1 and `2 must bound the marked cell, shown striped on the right picture. Moreover, that cell is bounded by four pseudolines. cells of the hourglass. In particular, the marked cell is bounded by at most four pseudolines, two of them being `i and `j …
Figure 9
Figure 9. Figure 9: Construction with n − 3 exit edges. Roudneff [21] and Harborth [16] proved that the upper bound n(n−1)/3 is tight for infinitely many values of n (see also [4]). The point sets that are dual to the currently-known arrangements that maximize the number of triangular cel…
Figure 10
Figure 10. Figure 10: An illustration of the proof of Theorem 2. [PITH_FULL_IMAGE:figures/full_fig_p014_10.png]
Figure 11
Figure 11. Figure 11: An illustration of the proof of Proposition 4. The path between [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]
Figure 12
Figure 12. Figure 12: Applying the dual transformation to the point set [PITH_FULL_IMAGE:figures/full_fig_p016_12.png]
Figure 13
Figure 13. Figure 13: Inserting the set of lines L + from S ∗ with positive slope that intersect the interior of 4. Left: the dashed line cannot be in L + since the intersection of s ∗ and t ∗ must be on the upper envelope. Thus, the lines in L + must intersect s ∗ on the boundary of 4. Ri…
Figure 14
Figure 14. Figure 14: Inserting the set of lines L − from S ∗ with negative slope that intersect the interior of 4+. Left: the dashed line cannot be in L − since the intersection of s ∗ and t˜∗ must be on the upper envelope. Thus, the lines in L − must intersect t˜∗ on the boundary of 4+. …
Figure 15
Figure 15. Figure 15: Top: two arrangements of 14 pseudolines with the same set of trian [PITH_FULL_IMAGE:figures/full_fig_p019_15.png]
Figure 16
Figure 16. Figure 16: Two arrangements of 20 pseudolines with the same set of triangular [PITH_FULL_IMAGE:figures/full_fig_p020_16.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 17 canonical work pages

  1. [1]

    Aichholzer

    O. Aichholzer. The order type database. Last accessed: Nov. 12,

    work page

  2. [2]

    Alamdari, P

    S. Alamdari, P. Angelini, F. Barrera-Cruz, T. M. Chan, G. Da Lozzo, G. Di Battista, F. Frati, P. Haxell, A. Lubiw, M. Patrignani, V. Roselli, S. Singla, and B. T. Wilkinson. How to morph planar graph drawings. SIAM J. Comput., 46(2):824–852, 2017.doi:10.1137/16M1069171

    work page doi:10.1137/16m1069171 2017

  3. [3]

    Bárány and Z

    I. Bárány and Z. Füredi. Empty simplices in Euclidean space.Can. Math. Bull., 30(4):436–445, 1987.doi:10.4153/CMB-1987-064-1

    work page doi:10.4153/cmb-1987-064-1 1987

  4. [4]

    J. Blanc. The best polynomial bounds for the number of triangles in a simple arrangement ofn pseudo-lines. InGeombinatorics, volume 21, pages 5–17, 2011. URL:https://edoc.unibas.ch/47402

    work page 2011

  5. [5]

    Onthecoordinatizationoforientedmatroids

    J.BokowskiandB.Sturmfels. Onthecoordinatizationoforientedmatroids. Discrete Comput. Geom., 1:293–306, 1986.doi:10.1007/BF02187702

    work page doi:10.1007/bf02187702 1986

  6. [6]

    S. Cabello. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl., 10(2):353–363, 2006. doi:10.7155/jgaa.00132

    doi:10.7155/jgaa.00132 2006

  7. [7]

    Cardinal, T

    J. Cardinal, T. M. Chan, J. Iacono, S. Langerman, and A. Ooms. Sub- quadratic encodings for point configurations.J. Comput. Geom., 10(2):99– 126, 2019. doi:10.20382/jocg.v10i2a6

    work page doi:10.20382/jocg.v10i2a6 2019

  8. [8]

    Chazelle, L

    B. Chazelle, L. J. Guibas, and D.-T. Lee. The power of geometric duality. BIT, (25):76–90, 1985.doi:10.1007/BF01934990

    doi:10.1007/bf01934990 1985

Show all 22 references
  1. [9]

    Dujmović

    V. Dujmović. The utility of untangling. J. Graph Algorithms Appl., 21(1):121–134, 2017.doi:10.7155/jgaa.00407

    2017 doi

  2. [10]

    Edelsbrunner, J

    H. Edelsbrunner, J. O’Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput., 15(2):341–363,

  3. [11]

    Felsner and J

    S. Felsner and J. E. Goodman. Pseudoline arrangements. In C. D. Tóth, J. O’Rourke, and J. E. Goodman, editors,Handbook of Discrete and Computational Geometry, pages 125–157. CRC Press, 3rd edition, 2017. doi:10.1201/9781315119601

    2017 doi

  4. [12]

    Felsner and H

    S. Felsner and H. Weil. A theorem on higher Bruhat orders. Discrete Comput. Geom., 23(1):121–127, 2000.doi:10.1007/PL00009485

    2000 doi

  5. [13]

    Füredi and I

    Z. Füredi and I. Palásti. Arrangements of lines with a large number of trian- gles. Proc. Am. Math. Soc., 92(4):561–566, 1984.doi:10.2307/2045427. JGAA, 0(0) 0–0 (0) 21

    1984 doi

  6. [14]

    J. E. Goodman and R. Pollack. Multidimensional sorting.SIAM J. Com- put., 12(3):484–507, 1983.doi:10.1137/0212032

    1983 doi

  7. [15]

    Grünbaum

    B. Grünbaum. Arrangements and spreads. AMS, 1972. URL: https: //bookstore.ams.org/cbms-10/

    1972

  8. [16]

    Harborth

    H. Harborth. Some simple arrangements of pseudolines with a maximum number of triangles. Ann. N. Y. Acad. Sci., 440(1):31–33, 1985. doi: 10.1111/j.1749-6632.1985.tb14536.x

    1985

  9. [17]

    F. Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudoger- ade. Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig, 78:256–267, 1926. In German

    1926

  10. [18]

    Ljubić, J.-P

    D. Ljubić, J.-P. Roudneff, and B. Sturmfels. Arrangements of lines and pseudolines without adjacent triangles.J. Comb. Theory. Ser. A, 50(1):24– 32, 1989. doi:10.1016/0097-3165(89)90003-4

    1989 doi

  11. [19]

    N. E. Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytope varieties. In Topology and Geometry—Rohlin Seminar, volume 1346 ofLecture Notes in Math., pages 527–544. Springer, 1988.doi:10.1007/BFb0082792

    1988 doi

  12. [20]

    G. Ringel. Teilungen der Ebene durch Geraden oder topologische Geraden. Math. Z., 64:79–102, 1956. In German.doi:10.1007/BF01166556

    1956 doi

  13. [21]

    J.-P. Roudneff. On the number of triangles in simple arrangements of pseudolines in the real projective plane.Discrete Math., 60:243–251, 1986. doi:10.1016/0012-365X(86)90016-6

    1986 doi

  14. [2020]

    URL: http://www.ist.tugraz.at/aichholzer/research/rp/ triangulations/ordertypes/

Pith tools

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