Proof of `Refined near-linear computation of Welzl orders`
groundedproofs/Lax457868Proofs/RefinedWelzlOrdersProof.lean · lax-457868
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The fixed compiled refined algorithm meets the stated crossing, time and success-probability bounds.
Proof strategy
The proof counts the actual finite fair-bit executions. It bounds initial retry cost and the accepted representative charge, then the chronological exception-repair loop, retaining every consumed random prefix. The maintained neighborhood separation supplies the paper's rejection bounds, and bounded selectors and retries supply the finite failure counts. The active-size contraction sums the round costs. The checked bounded clock and compiler transfer give the public word-RAM contract with success probability at least two thirds, including the complete small-input branch.
Attribution
The algorithm and refined parameters follow the supplied refined manuscript. The graph encoding, reconstruction and machine infrastructure reuse the original Welzl-order submission and the registered word-RAM compiler.