Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity

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}(\mathrm{\mid }U{\mathrm{\mid }}^3\mathrm{\mid }\mathcal{F}\mathrm{\mid })$ bound, through Har-Peled’s $\mathcal{O}(\mathrm{\mid }U{\mathrm{\mid }}^2\mathrm{\mid }\mathcal{F}\mathrm{\mid })$, to the recent sampling-based methods of Csikós 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}(\mathrm{\parallel }S\mathrm{\parallel }\log \mathrm{\parallel }S\mathrm{\parallel })$, where $\mathrm{\parallel }S\mathrm{\parallel }=\mathrm{\mid }U\mathrm{\mid }+{\sum }_{X\in \mathcal{F}}\mathrm{\mid }X\mathrm{\mid }$ 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+\epsilon })$ to $\mathcal{O}(n^{3+\epsilon })$.