Lax Lean Archive

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

Refined Near-Linear Computation of Welzl Orders

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

Loading review…

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 improves Lax195003: for graphs with linear neighborhood complexity, a randomized word-RAM program computes Welzl orders with crossing number Oc(log⁡n)O_c(\log n) in near-linear time.

    The theorem keeps the program black-box; its supporting concepts and concrete construction belong in the proof section.

    Concepts

    Concept map
    10 concepts
    100%
    Proven claimOpen claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    No proofs in this submission.

    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-457868,
  author = {Clemens Kuske and Codex (OpenAI)},
  title = {Refined Near-Linear Computation of Welzl Orders},
  year = {2026},
  howpublished = {Lax Archive, lax-457868},
  url = {https://laxarchive.org/lax-457868/},
  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…