Maximum Rectilinear Crossing Number of Uniform Hypergraphs

Ayan; Rahul Gangopadhyay

REVIEW 4 major objections 6 minor 20 references

Maximum Rectilinear Crossing Number of Uniform Hypergraphs

T0 review · 4 major / 6 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 This paper proves that the maximum number of crossing pairs in a 4-dimensional rectilinear drawing of the complete 4-uniform hypergraph on n vertices is exactly 13 times the number of 8-vertex subsets.

desk verdict Real results and useful techniques, but the abstract overclaims, Theorem 2 is misstated, the proof of Theorem 4's upper bound has a gap, and the d=4 constant rests on an insufficiently documented computation. read the letter →

arxiv 1908.04654 v6 pith:WWIQYGVY submitted 2019-08-13 math.CO

Rahul Gangopadhyay , Ayan This is my paper · ORCID

classification math.CO MSC 05C6552B11

keywords rectilinearcrossingnumberGaletransformmomentcurveneighborlypolytopecompleteuniformhypergraphordertypesNP-hardnessdrawing

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 studies how many pairs of hyperedges can cross when a d-uniform hypergraph is drawn with straight (d-1)-simplices in R^d. Its headline result is exact: in any 4-dimensional rectilinear drawing of the complete 4-uniform hypergraph on n vertices, every 8 vertices contribute at most 13 crossing pairs, and placing the vertices on the 4-dimensional moment curve attains 13 for every 8-set, so the maximum total is 13*C(n,8). This settles the d=4 case of a conjecture about convex drawings, and does so for all rectilinear drawings, not just convex ones. Along the way the paper improves the lower bound for K^d_{2d} to $\Omega$(2^d d), proves a 3-dimensional lower bound of (43/42)C(n,6) for $K^{3}$_n, determines the maximum for balanced complete d-partite d-uniform hypergraphs, shows the general maximization problem is NP-hard, and gives a randomized constant-factor approximation.

What carries the argument

The key machinery is the Gale transform and its affine Gale diagram. The Gale transform is a linear-algebraic encoding of a point configuration: n points spanning R^d become n vectors spanning $R^{{n-d-1}}$ that sum to zero; the affine Gale diagram projects these onto a hyperplane and colors by direction, yielding for 8 points in $R^{4}$ a set of 4 red and 4 blue planar points. Its role is to convert geometric crossings into combinatorial separations: a pair of vertex-disjoint hyperedges crosses exactly when a linear hyperplane separates their Gale vectors into opposite open half-spaces, and for 4 points in $R^{4}$ this becomes counting balanced 2-sets and balanced 4-sets of a bicolored planar point set. This reduction turns Theorem 3 into a finite enumeration over all order types and colorings, and also gives a clean characterization of when a Gale diagram comes from a neighborly 4-polytope.

What would settle it

Run an independent exhaustive enumeration of all oriented matroids of rank 5 on 8 elements, equivalently all order types of 8 planar points, together with all 70 balanced 4-4 colorings, and check whether any Gale diagram has more than 12 balanced 2-sets plus balanced 4-sets; finding one would give a 4D drawing of $K^{4}$_8 with 14 crossings and refute Theorem 3.

Watch

Extended reading notes

Core claim

The central quantitative discovery is the local bound behind Theorem 3. Using the Gale transform, a drawing of $K^{4}$_8 corresponds to an affine Gale diagram: 4 red and 4 blue points in general position in the plane. Crossings of disjoint 3-simplex pairs are exactly proper linear separations of the Gale transform, and Observation 2 counts these as balanced 2-sets plus balanced 4-sets plus 1. An exhaustive check over all 3315 order types of 8 planar points and all 70 balanced red/blue colorings shows the sum of balanced 2-sets and balanced 4-sets is at most 12, hence at most 13 crossings per 8 vertices; the alternating red/blue coloring of a convex octagon attains 12, and placing the original 8 points on the moment curve realizes 13. Scaling to n vertices gives max-cr4($K^{4}$_n)=13*C(n,8), and the same Gale-diagram conditions show any 4-dimensional neighborly polytope with vertices in general position achieves the bound.

Load-bearing premise

The upper bound in Theorem 3 assumes that the computer-generated catalogue of all planar order types of 8 points is complete and that every feasibility check in the posted enumeration code is correct; if either fails, a drawing of $K^{4}$_8 with 14 crossings could exist.

Editorial extensions

If this is right

For d=4, the conjecture of Anshu et al. is true, and in the stronger form: all rectilinear drawings, not only convex ones, are bounded by 13*C(n,8).
Moment-curve placements, equivalently vertices of a 4-dimensional neighborly polytope in general position, are exact maximizers for max-cr4(K^4_n).
Every 8-vertex subset of any 4D rectilinear drawing contributes at most 13 crossing pairs, giving a clean additive local bound over n.
The new counting argument improves the lower bound for K^d_{2d} from Omega(2^d sqrt(d)) to Omega(2^d d) and gives cr3(K^3_n) >= (43/42)C(n,6).
For complete d-partite balanced d-uniform hypergraphs the maximum is exactly (2^{d-1}-1)*C(n,2)^d, and the general maximum problem is NP-hard with a randomized constant-factor approximation.

Reading between the lines

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

One natural extension, not asserted by the paper, is that the same Gale-diagram counting could be pushed to higher dimensions: if every d-dimensional neighborly polytope has a local per-(2d)-vertex crossing number equal to the moment-curve value, the conjecture for all d would follow from identifying the extremal Gale diagrams.
The exhaustive 8-point enumeration suggests a practical check: independently regenerating the order-type catalogue with different software would test the completeness assumption behind the 13 bound.
The NP-hardness reduction resembles a geometric Max-Cut; the randomized approximation factor c~d may be improvable, and derandomizing higher d is a natural next step given that d=2 has already been derandomized.
If the exact 13-per-8 bound transfers to arbitrary 4-uniform hypergraphs, it would give a simple upper bound on max-cr4(H) proportional to the number of 8-vertex subsets, which could support algorithmic upper bounds.

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.

Desk Editor's Note

read the letter

Two things you should know up front. This paper contains real new results: the d=4 resolution of the Anshu et al. conjecture via Gale transforms, an exact formula for balanced complete d-partite hypergraphs, NP-hardness, and a randomized constant-factor approximation. It also has avoidable statement errors and one genuine proof gap that prevents it from being taken at face value.

What's good: The Gale transform route is the right one for the d=4 problem, and the reduction from a 4D drawing problem to a finite enumeration over 3315 order types times 70 colorings is sound in spirit. The code is shipped, which is more than most papers do. The NP-hardness reduction is a standard gadget and looks correct. The randomized approximation analysis is also fine.

Soft spots, in order of severity.

First, the abstract claims a lower bound of Omega(((4 sqrt 2)/3^{3/4})^d / d) for cr_d(K^d_{2d}), but Theorem 1 in the body proves only Omega(2^d d). One of these is wrong; the body's bound is what the counting argument supports.

Second, Theorem 2 is stated as an equality, cr_3(K^3_n)=43/42 * C(n,6), but the proof establishes a lower bound. The abstract correctly says 'at least'. The theorem statement needs to be corrected.

Third, and more serious: Lemma 11 is used in Lemma 13 to claim that the maximum number of crossing transversals in K^d_{d x 2} is 2^{d-1}-1. But Lemma 11 only says at least one transversal crosses; it does not rule out all 2^{d-1} crossing. The bucket analysis shows the moment-curve drawing attains 2^{d-1}-1, but there is no upper bound argument for arbitrary drawings. As printed, Theorem 4 is a lower bound construction, not an exact maximum.

Fourth, the proof of Theorem 3 depends on the count of balanced sets in the affine Gale diagram. Observation 2 states the number of proper linear separations equals balanced 2-sets + balanced 4-sets + 1. The code, however, counts only one 4-set from each complementary pair (it tests 35 4-combinations, not 70), so the identity in the text is off by a factor of two on the 4-set term. The code's arithmetic gives the right crossing number, but the stated lemma is false as written and needs a clarification that balanced 4-sets are counted modulo complement.

Fifth, the decisive finite check—maximum balanced sets = 12—rests on the completeness of Aichholzer's order-type database and on a Python/GLPK enumeration with weak inequalities. The paper reports no per-order-type maxima and no independent verifier. This is a testable computational claim, and a referee should re-run it, but as is, the constant 13 in Theorem 3 is only as good as that script.

Bottom line: this is a paper for crossing-number and geometric hypergraph people. The Gale transform framework and the NP-hardness reduction are worth keeping. But I would not trust Theorem 4 as an exact result until the upper bound appears, and Theorem 3 needs the computational step independently checked and the Observation 2 statement fixed. Send it to a serious referee, but expect major revision.

Referee Report

4 major / 6 minor

Summary. The paper studies the maximum d-dimensional rectilinear crossing number of uniform hypergraphs. It claims an improved lower bound for cr_d(K^d_{2d}), a lower bound for the 3-dimensional rectilinear crossing number of K^3_n, an exact formula max-cr_4(K^4_n)=13 C(n,8), an exact formula for balanced complete d-partite d-uniform hypergraphs, NP-hardness of the maximum crossing number problem for arbitrary d-uniform hypergraphs, and a randomized constant-factor approximation. The main tool for the d=4 result is the Gale transform, order-type enumeration, and a finite computational check; the other results use geometric lemmas and reductions from MAX-EK-set splitting.

Significance. If the main claims are correct, the paper makes several substantial contributions: it settles Anshu et al.'s moment-curve conjecture for d=4 with an exact formula, gives a new lower bound for cr_3(K^3_n), improves the lower bound for cr_d(K^d_{2d}), and adds NP-hardness and approximation results for maximum rectilinear crossing numbers. The randomized approximation scheme and the NP-hardness reduction are conceptually clean and appear sound. The exact d=4 statement is the paper's flagship result, but it depends on a finite computation whose reproducibility and certification are presently incomplete; the manuscript does ship code, but not the external data or an independent verifier.

major comments (4)

[§3, Theorem 1 and §2.2, Lemma 5] The abstract claims the lower bound Ω(((4√2/3^{3/4})^d)/d), while Theorem 1 and its proof in Section 3 claim only Ω(2^d d); these are different bounds and the proof does not establish the abstract statement. In addition, Lemma 5 as printed is impossible: it asserts pairs of disjoint subsets of C′ of size ⌊(d+2)/2⌋ whose union is C′, but two such subsets have total size at most d+2, whereas |C′|=d+4. The proof of Theorem 1 later uses partitions with sizes summing to d+4, so the lemma statement needs correction and the extension-counting step must be reconciled with the stated bound.
[§3, Theorem 2] Theorem 2 is stated as an equality, cr_3(K^3_n)=43/42 C(n,6), but the proof establishes only a lower bound: it shows cr_3(K^3_9)≥86 and then averages to obtain cr_3(K^3_n)≥43/42 C(n,6). No drawing with exactly 43/42 C(n,6) crossings is exhibited, so the nontrivial upper bound for the minimum crossing number is missing. The abstract's wording 'at least' is accurate; the theorem statement in the body should be changed to a lower bound or supplemented with a matching construction.
[§4, proof of Theorem 3 and Appendix] The exact constant 13 in Theorem 3 rests entirely on the finite assertion that over the 3315 planar order types of 8 points and 70 red/blue colorings, the maximum of balanced 2-sets plus balanced 4-sets is 12. The only support is the Python/GLPK code in the Appendix, which depends on an external order-type database that is not shipped, reports no per-order-type maximums, and uses floating-point LP feasibility with weak inequalities (≥1 and ≤1); a parsing, database, or near-degenerate feasibility error would change the constant. Furthermore, the printed code tests only the 35 4-subsets that contain the first vertex, while Observation 2 as written counts all balanced 4-sets; unless the fixed-vertex convention is stated, the formula overcounts each proper separation. Please provide an exact-arithmetic verifier, the input data or a cryptographic hash of it, a summary table of maxima, and a precise statement of the counting convention used in Observation 2.
[§4, Lemma 13 and proof of Theorem 4] The upper bound in Lemma 13 is derived by writing that Lemma 11 implies the existence of a pair of disjoint simplices and that this implies at most 2^{d-1}-1 of the 2^{d-1} complementary pairs can cross. This inference is valid only if 'disjoint' means non-crossing in the sense of disjoint relative interiors; if it merely means vertex-disjoint, the existence of one crossing pair gives no upper bound. The manuscript uses both meanings elsewhere. Please define 'disjoint simplices' in this lemma and supply a proof or a precise reference that at least one of the 2^{d-1} pairs does not cross in every drawing.

minor comments (6)

[§4, first paragraph] The sentence 'We also produce a family of 4-dimensional rectilinear drawings of K^4_n having 13 C(n,4) crossing pairs' should read C(n,8), since each crossing pair uses 8 vertices.
[§5, table of c̃_d values] The table entry '13/355/14' appears to be a typesetting error; it should likely be '13/35, 5/14'.
[§2.2, Lemmas 5 and 6] Lemmas 5 and 6 are cited from the self-authored preprint [10] and are load-bearing for Theorem 1; if they are not published elsewhere, proofs should be included in an appendix or the reference should be updated.
[§4, proof of Lemma 12] The proof states that the value 12 was found for all members of O′ but the printed Appendix code does not appear to output this aggregate value; including the computed maxima for all qualifying order types would make the claim checkable.
[§4, Observation 2] The phrase 'the total number of balanced 4-sets' is ambiguous because the complement of a balanced 4-set is also a balanced 4-set and corresponds to the same proper linear separation; the proof should state explicitly that each separation is represented once, e.g., by the side containing a distinguished vertex.
[Throughout] There are several minor grammatical slips, such as 'having all its 8 in general position' in the proof of Lemma 12, which should read 'having all its 8 vertices in general position'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main derivations are self-contained reductions via Gale transforms and external order-type enumeration; self-citations are independent prior results, not inputs to the target claims.

full rationale

The paper's central result, max-cr4(K^4_n)=13*C(n,8), is not circular. The exact constant 13 is obtained by applying the Gale transform, which maps crossing pairs of hyperedges bijectively to proper linear separations (Lemma 3, Matousek), and then by reducing those separations to balanced 2-sets, balanced 4-sets, and the trivial balanced 0-set (Observation 2). The remaining finite maximum of 12 balanced sets is determined by an exhaustive enumeration over the 3315 order types from the external Aichholzer database and all 70 red/blue colorings. This is a finite computation over the input data, not a parameter fitted so as to force the claimed constant; the claimed value 13 is the output of the enumeration, not an assumption. The lower bound is supplied independently by the moment-curve construction from Anshu et al. The proof then extends from K^4_8 to K^4_n by a disjointness count over 8-vertex subsets, which is a direct combinatorial argument. The other theorems are also non-circular. Theorem 1 cites Lemmas 5 and 6 from a self-authored preprint, but those lemmas are stated as general-position intersection facts about subsets of size d+4 and 2d; they do not contain the target lower bound Ω(2^d d), and the double-counting argument that converts them into the new bound is carried out in this paper. The use of Lemmas 7-11 and the moment-curve formula from Anshu et al. is likewise reliance on independent, parameter-free prior results rather than a reduction of the conclusions to their own inputs. The computational enumeration in the appendix is a possible correctness risk if the order-type database or the LP feasibility tests are flawed, but a computational dependency is not circularity. No equation or definition in the paper is shown to be equivalent, by construction, to the result it is used to prove.

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

No free parameters or invented entities appear. The paper imports standard Gale-transform facts and several external geometric theorems. The two most fragile imports for the new results are the self-authored lemmas used in Theorem 1 and the order-type database completeness assumption for Theorem 3.

assumptions (5)

standard math Gale transform characterization: a sequence of n vectors in R^(n-d-1) is a Gale transform of n points in R^d if and only if it spans R^(n-d-1) and its vectors sum to zero; separations correspond to convex hull crossings.
Invoked through Lemmas 1-4 from Matousek and Grünbaum in the proof of Theorem 3 and Lemma 12. This is the bridge between geometric crossings and balanced set counts.
domain assumption The Aichholzer order-type database lists all 3315 order types of 8 points in general position in the plane.
Theorem 3's exhaustive computer upper bound depends on the completeness of this external database; the manuscript links to it but does not prove completeness.
domain assumption Lemmas 5 and 6 from the authors' earlier preprint (arXiv:1806.02574) are correct: every (d+4)-point subset yields floor((d+4)/2) crossing sub-simplex pairs, and each extends to many full hyperedge crossings.
Theorem 1's improved lower bound is built directly on these two self-cited lemmas, which are not reproved or machine-checked in this manuscript.
standard math Akiyama-Alon disjoint simplices theorem: for d pairwise disjoint n-point sets in R^d in general position there exist n pairwise disjoint (d-1)-simplices, one vertex from each set.
Used in Lemma 13 to force at least one non-crossing complementary pair in K^d_{d×2}, giving the upper bound in Theorem 4.
standard math Bisztriczky-Soltan theorem: every set of 9 points in general position in R^3 contains 6 points in convex position.
Used in the proof of Theorem 2 to locate a convex K^3_6 inside any drawing of K^3_9.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Maximum Rectilinear Crossing Number of Uniform Hypergraphs." pith.science (2026). https://pith.science/paper/WWIQYGVY

@misc{pith2026190804654,
  author       = {Pith},
  title        = {Pith review of: Maximum Rectilinear Crossing Number of Uniform Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WWIQYGVY}},
  note         = {Machine review of arXiv:1908.04654}
}

abstract

We improve the lower bound on the $d$-dimensional rectilinear crossing number of the complete $d$-uniform hypergraph having $2d$ vertices to $\Omega\left(\dfrac{(4\sqrt{2}/3^{3/4})^d}{d}\right)$ from $\Omega(2^d \sqrt{d})$. We also establish that the $3$-dimensional rectilinear crossing number of a complete $3$-uniform hypergraph having $n \geq 9$ vertices is at least $\dfrac{43}{42}\dbinom{n}{6}$. We prove that the maximum number of crossing pairs of hyperedges in a $4$-dimensional rectilinear drawing of the complete $4$-uniform hypergraph having $n$ vertices is $13\dbinom{n}{8}$. We also prove that among all $4$-dimensional rectilinear drawings of a complete $4$-uniform hypergraph having $n$ vertices, the number of crossing pairs of hyperedges is maximized if all its vertices are placed at the vertices of a $4$-dimensional neighborly polytope. Our result proves the conjecture by Anshu et al. [Anshu, Gangopadhyay, Shannigrahi, and Vusirikala, 2017] for $d=4$. We prove that the maximum $d$-dimensional rectilinear crossing number of a complete $d$-partite $d$-uniform balanced hypergraph is $(2^{d-1}-1){\dbinom{n}{2}}^d$. We then prove that finding the maximum $d$-dimensional rectilinear crossing number of an arbitrary $d$-uniform hypergraph is NP-hard. We give a randomized scheme to create a $d$-dimensional rectilinear drawing of a $d$-uniform hypergraph $H$ such that, in expectation the total number of crossing pairs of hyperedges is a constant fraction of the maximum $d$-dimensional rectilinear crossing number of $H$.

Figures

Figures reproduced from arXiv: 1908.04654 by the authors.

**Figure 1.** An affine gale diagram of 8 points in R 4 Let us define a Balanced 2m-set for a planar point set having an equal number of blue and red points in general position in R 2 . Balanced 2m-set: Let T be a set of n red and n blue points in R 2 such that all the 2n points are in general position. A balanced 2m-set of T is a subset X ⊆ T of size 2m that can be separated from the rest of the (2n − 2m) points by a line and X… view at source ↗

**Figure 2.** Possible orientations of a triplet in R 2 Order-type: Consider a sequence of points S 0 = hs 0 1 , s0 2 , . . . , s0 n i where points are in general position in R 2 . The order-type of s 0 is a mapping which assigns an orientation (clockwise or counter-clockwise) to each ordered triple hs 0 i , s0 j , s0 k i. Consider two sequences of points S 0 = hs 0 1 , s0 2 , . . . , s0 n i and S 00 = hs 00 1 , s00 2 , . . . , s… view at source ↗

**Figure 3.** Non-crossing pair of hyperedges of K4 4×2 When d is odd, the number of disjoint vertex sets {A, B} that do not contain any subsequence of alternating chain of d + 2 vertices is equal to the number of ways d vertices of B can be distributed among the d buckets created by the vertices of A such that at most bd/2c of the first (d − 1) buckets are non-empty. Since the last bucket can contain at most one vertex of B and … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: 3-dimensioanal Rectilinear Drawing of a 3 uniform hypergraph [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Aichholzer

O. Aichholzer. Order Types for Small Point Sets. http://www.ist.tugraz.at/staﬀ/aichholzer/research/rp/triangulations/ordertypes/

work page
[2]

Aichholzer, F

O. Aichholzer, F. Aurenhammer and H. Krasser. Enumerating order types for small point sets with applications. Order 19, 265-281 (2002)

work page 2002
[3]

Akiyama and N

J. Akiyama and N. Alon. Disjoint simplices and geometric hypergraphs. Annals of the New York Academy of Sciences 555, 1-3 (1989)

work page 1989
[4]

Anshu, R

A. Anshu, R. Gangopadhyay, S. Shannigrahi and S. Vusirikala. On the rectilinear crossing number of complete uniform hypergraphs. Computational Geometry: Theory and Applications 61, 38-47 (2017)

work page 2017
[5]

S. Bald, M. P. Johnson and O. Liu. Approximating the maximum rectilinear crossing number. In Proceedings of International Computing and Combinatorics Conference. Springer, 455-467(2016)

work page 2016
[6]

M. Breen. Primitive Radon partitions for cyclic polytopes. Israel Journal of Math- ematics 15, 156-157 (1973)

work page 1973
[7]

Bisztriczky and V

T. Bisztriczky and V. Soltan. Some Erd˝ os-Szekeres type results about points in space, Monatshefte f¨ ur Mathematik 118, 33-40 (1994)

work page 1994
[8]

T. K. Dey and J. Pach. Extremal problems for geometric hypergraphs. Algorithms and Computation (Proc. ISAAC ’96, Osaka; T. Asano et al., eds.), Lecture Notes in Computer Science 1178, Springer-Verlag, 105-114 (1996). Also in: Discrete and Computational Geometry 19, 473-484 (1998)

work page 1996

Show all 20 references

[9]

D. Gale. Neighboring vertices on a convex polyhedron. Linear inequalities and re- lated system 38, 255-263 (1956)

1956
[10]

Gangopadhyay and S

R. Gangopadhyay and S. Shannigrahi. k-Sets and Rectilinear Crossings in Com- plete Uniform Hypergraphs. arXiv preprint arXiv:1806.02574 (2018)

2018 arXiv
[11]

Gr¨ unbaum

B. Gr¨ unbaum. Convex Polytopes. Springer, 2003

2003
[12]

Matouˇ sek

J. Matouˇ sek. Lectures in Discrete Geometry. Springer, 2002

2002
[13]

Lov´ asz

L. Lov´ asz. Coverings and colorings of hypergraphs. In Proceedings of the 4th South- eastern Conference on Combinatorics, Graph Theory and Computing. Utilitas Math- ematica Publishing, 3-12 (1973)

1973
[14]

G. Ringel. Extremal problems in the theory of graphs. In Proceedings of Theory of Graphs and its Applications, 85-90 (1964)

1964
[15]

Schaefer

M. Schaefer. The graph crossing number and its variants: A survey. The electronic journal of combinatorics 1000, 21-22 (2013)

2013
[16]

Verbitsky

O. Verbitsky. On the obfuscation complexity of planar graphs. Theoretical Com- puter Science 396, 294-300 (2008)

2008
[17]

p o i n t _ s e t _ h e x . txt

G. M. Ziegler. Lectures on Polytopes. Springer, 1995. Maximum Rectilinear Crossing Number of Uniform Hypergraphs 21 7 Appendix Here we give our programs that were used to prove Theorem 3. The source code contains multiple ﬁles. This has been done to make it more readable and m...

1995
[19]

a l l _ p o i n t _ s e t s . txt

, 35) ) with open ( " a l l _ p o i n t _ s e t s . txt " , " r " ) as ptsfile : a l l p t s _ s t r = ptsfile . r ea dl ine s () line_no = 1 for line in a l l p t s _ s t r : # # C o n v e r t i n g point set from string to usable list of tuples p o i n t s e t _ d e t a i l ...
[20]

run . mod

) . d i f f e r e n c e ( indices ) ) combo , r e m a i n i n g _ p o i n t s = [] , [] for index in indices : combo . append ( po in t_ se t [ index ]) for index in r e m a i n i n g _ i n d i c e s : r e m a i n i n g _ p o i n t s . append ( po in t_ se t [ index ]) # # G e...
[177]

def run () : # # Reading the file and saving it as a list of strings with open (

, (55 , 210) , (243 , 53) , " def run () : # # Reading the file and saving it as a list of strings with open ( " ./ p o i n t _ s e t _ h e x . txt " , " r " ) as hexfile : hexlines = hexfile . r ea dl in es () a l l _ p o i n t _ c o o r d i n a t e s = [] for line in hexline...

Pith tools

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

[1] [1]

Aichholzer

O. Aichholzer. Order Types for Small Point Sets. http://www.ist.tugraz.at/staﬀ/aichholzer/research/rp/triangulations/ordertypes/

work page

[2] [2]

Aichholzer, F

O. Aichholzer, F. Aurenhammer and H. Krasser. Enumerating order types for small point sets with applications. Order 19, 265-281 (2002)

work page 2002

[3] [3]

Akiyama and N

J. Akiyama and N. Alon. Disjoint simplices and geometric hypergraphs. Annals of the New York Academy of Sciences 555, 1-3 (1989)

work page 1989

[4] [4]

Anshu, R

A. Anshu, R. Gangopadhyay, S. Shannigrahi and S. Vusirikala. On the rectilinear crossing number of complete uniform hypergraphs. Computational Geometry: Theory and Applications 61, 38-47 (2017)

work page 2017

[5] [5]

S. Bald, M. P. Johnson and O. Liu. Approximating the maximum rectilinear crossing number. In Proceedings of International Computing and Combinatorics Conference. Springer, 455-467(2016)

work page 2016

[6] [6]

M. Breen. Primitive Radon partitions for cyclic polytopes. Israel Journal of Math- ematics 15, 156-157 (1973)

work page 1973

[7] [7]

Bisztriczky and V

T. Bisztriczky and V. Soltan. Some Erd˝ os-Szekeres type results about points in space, Monatshefte f¨ ur Mathematik 118, 33-40 (1994)

work page 1994

[8] [8]

T. K. Dey and J. Pach. Extremal problems for geometric hypergraphs. Algorithms and Computation (Proc. ISAAC ’96, Osaka; T. Asano et al., eds.), Lecture Notes in Computer Science 1178, Springer-Verlag, 105-114 (1996). Also in: Discrete and Computational Geometry 19, 473-484 (1998)

work page 1996