rectilinear_crossing_number
For a finite set P of points in the plane ℝ × ℝ, the rectilinear crossing number of P is the number of unordered pairs of disjoint 2-element subsets {e₁, e₂} of P whose open line segments have nonempty intersection.
Statement
noncomputable def rectilinear_crossing_number (P : Finset (ℝ × ℝ)) : ℕ
- Defined in
- arXiv:2610.38658, Section 4
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Used by 3
- rectilinear_crossing_number_add_total_simplicial_depth_eq_choose_of_fourIf every 4-element subset Q of a finite point set P in the Euclidean plane satisfies cr(Q) + TSD(Q) = 1, then cr(P) + TSD(P) = (|P| choose…
- rectilinear_crossing_number_emptyThe rectilinear crossing number of the empty set of points in the real plane ℝ × ℝ is 0.
- rectilinear_crossing_number_eq_sum_powersetCard_fourThe rectilinear crossing number of a finite point set P in the Euclidean plane is the sum over all 4-element subsets Q of P of the…
Read back from the Lean
Given a finite set of points $P \subset \mathbb{R} \times \mathbb{R}$, rectilinear_crossing_number P is the number of pairs $\{e_1, e_2\}$ of distinct 2-element subsets of $P$ (edges of the complete graph on $P$) such that:
1. $e_1$ and $e_2$ are disjoint (they share no vertices in $P$), and
2. there exist distinct vertices $u_1, v_1 \in e_1$ and distinct vertices $u_2, v_2 \in e_2$ such that the open line segment between $u_1$ and $v_1$ has a nonempty intersection with the open line segment between $u_2$ and $v_2$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Rectilinear crossing number of a finite point set P in ℝ × ℝ. -/ noncomputable def rectilinear_crossing_number (P : Finset (ℝ × ℝ)) : ℕ := open Classical in (((P.powersetCard 2).powersetCard 2).filter (fun (pair : Finset (Finset (ℝ × ℝ))) => ∃ e₁ ∈ pair, ∃ e₂ ∈ pair, e₁ ≠ e₂ ∧ Disjoint e₁ e₂ ∧ ∃ u₁ ∈ e₁, ∃ v₁ ∈ e₁, ∃ u₂ ∈ e₂, ∃ v₂ ∈ e₂, u₁ ≠ v₁ ∧ u₂ ≠ v₂ ∧ (openSegment ℝ u₁ v₁ ∩ openSegment ℝ u₂ v₂).Nonempty)).card