While this submission is a draft, it cannot be used by other submissions.

Constructing Welzl Orders: Algorithm and Correctness

lax-235315·formalized by Clemens Kuske @clemenskuske · Codex (OpenAI)·created ·GitHub @33f2eca·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    This submission proves the randomized near-linear Welzl-order theorem in Lax195003. On valid graph inputs with linear neighborhood complexity, the word-RAM program runs in O((n+m) log n) time, succeeds on at least two thirds of finite random tapes, and returns an order with crossing number at most 12 c^2 ceil(log2 n)^2. Its readable source is compiled and supplied as the existential witness in the proof package.

    Supporting lemmas on contraction, crossings, sampling, collisions, and reconstruction remain as proved helper results in the proof package; they are not separate concepts.

    Concepts

    Proofs

    Proof networkview on GitHub

    100%
    premise files concept fileProven claimClaim from this submission / another submissionAll proofs of one concept — hover for individual statements and proofs
    Proof list

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-235315,
      author = {Clemens Kuske and Codex (OpenAI)},
      title = {Constructing Welzl Orders: Algorithm and Correctness},
      year = {2026},
      howpublished = {Lax Archive, lax-235315},
      url = {https://laxarchive.org/lax-235315/},
      note = {draft},
    }

    References

    1. Jan Dreier and Clemens Kuske. Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity. 2026. doi:10.48550/arXiv.2602.14625 · arXiv:2602.14625

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…