greedyMatching
def
Given a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P across pts starting from the empty matching ∅ : Finset (Sym2 (ℝ × ℝ)) and empty unmatched list [].
Statement
noncomputable def greedyMatching (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (pts : List (ℝ × ℝ)) : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)
- Defined in
- arXiv:2610.23130, Section 1
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Built on 1
- greedyStepGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2…
- Used by 5
- greedy_matching_ratio_equiv_blocking_boundsTheorem 1.2 (arXiv:2610.23130): Let P be a hereditary segment crossing property. (1) If the blocking number β_P(ℓ) ≤ p (every family of ℓ…
- not_greedy_fraction_le_of_blocking_geThe statement
greedy_fraction_le_of_blocking_geis false: The statement is false as written; a machine-checked refutation is provided.… - greedy_matching_fraction_ge_of_blocking_leLet P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list…
- greedy_matching_fraction_le_of_blocking_geLet P be a hereditary segment property. If β_P(ℓ) ≥ p (formalized by segment_blocking_bound_ge P ℓ p), then there exists a duplicate-free…
- greedyMatching_nilFor every predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in ℝ × ℝ, greedyMatching P [] equals the…
Read back from the Lean
greedyMatching is a definition taking a predicate P on finite sets of unordered pairs of points in ℝ² (P : Finset (Sym2 (ℝ × ℝ)) → Prop) and a list of points pts : List (ℝ × ℝ), returning a pair (M, U) : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ). It is defined as the left-fold of greedyStep P over pts starting with the accumulator (∅, []).
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
/-- The greedy online geometric matching algorithm on an input sequence of points. -/ noncomputable def greedyMatching (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (pts : List (ℝ × ℝ)) : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ) := pts.foldl (greedyStep P) (∅, [])