greedyStep
Given a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2 (ℝ × ℝ)) and a list of unmatched points U : List (ℝ × ℝ), and an arriving point v : ℝ × ℝ, greedyStep searches U in order for the first point u such that P holds on the insertion of s(u, v) into M; if found, it returns (insert s(u, v) M, U.erase u), and if no such u exists, it returns (M, U ++ [v]).
Statement
noncomputable def greedyStep (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (state : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)) (v : ℝ × ℝ) : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)
- Defined in
- arXiv:2610.23130, Section 1
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Used by 4
- greedyMatchingGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P…
- 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…
Read back from the Lean
greedyStep is a noncomputable definition that takes:
1. a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in $\mathbb{R}^2$,
2. a state state = (M, U) where M is a finite set of unordered pairs of points in $\mathbb{R}^2$ (Finset (Sym2 (ℝ × ℝ))) and U is a list of points in $\mathbb{R}^2$ (List (ℝ × ℝ)), and
3. a point v : ℝ × ℝ,
and returns an updated pair (M', U') : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ) defined as follows:
- It searches the list U for the first element u such that P (insert s(u, v) M) holds (where s(u, v) is the unordered pair of u and v).
- If such a u is found, it returns (insert s(u, v) M, U.erase u) (inserting the edge {u, v} into M and erasing the first occurrence of u from U).
- If no such u exists in U, it returns (M, U ++ [v]) (leaving M unchanged and appending v to the end of U).
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
/-- One step of the greedy matching algorithm upon arrival of a new point v. -/ noncomputable def greedyStep (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (state : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)) (v : ℝ × ℝ) : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ) := open scoped Classical in let (M, U) := state match U.find? (fun u => P (insert s(u, v) M)) with | some u => (insert s(u, v) M, U.erase u) | none => (M, U ++ [v])