Orders with low crossing number, introduced by Welzl, are a fundamental tool in range searching and computational geometry. Recently, they have found important applications in structural graph theory: set systems with linear shatter functions correspond to graph classes with linear neighborhood complexity. For such systems, Welzl's theorem guarantees the existence of orders with only $\mathcal{ O}(\log^2 n)$ crossings. A series of works has progressively improved the runtime for computing such orders, from Chazelle and Welzl's original $\mathcal{ O}(|U|^3 |\mathcal{ F}|)$ bound, through Har-Peled's $\mathcal{ O}(|U|^2|\mathcal{ F}|)$, to the recent sampling-based methods of Csik\'os and Mustafa. We present a randomized algorithm that computes Welzl orders for set systems with linear primal and dual shatter functions in time $\mathcal{ O}(\|S\| \log \|S\|)$, where $\|S\| = |U| + \sum_{ X \in \mathcal{ F}} |X|$ is the size of the canonical input representation. As an application, we compute compact neighborhood covers in graph classes with (near-)linear neighborhood complexity in time \(\mathcal{ O}(n \log n)\) and improve the runtime of first-order model checking on monadically stable graph classes from $\mathcal{ O}(n^{ 5+\varepsilon})$ to $\mathcal{ O}(n^{ 3+\varepsilon})$.
Categories: cs.DS