Constructing Welzl Orders: Algorithm and Correctness
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
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
Proof list
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
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
- 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.
0 comments