An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs

The vast majority of hypergraphs that arise in discrete and computational geometry, describe semi-algebraic relations between elementary geometric objects. We use the polynomial method of Guth and Katz to establish stronger and more efficient regularity and density theorems for such k-uniform hypergraphs H = (P, E), where P is a finite point set in R d , and the edge set E is determined by a semi-algebraic relation of bounded description complexity.

In particular, for any 0 < ǫ ≤ 1 we show that one can construct in O (n log 1/ǫ) time, an equitable partition P = U 1 ⊎. . .⊎U K into K = O(1/ǫ d+1+δ ) subsets, for any 0 < δ, so that all but ǫ-fraction of the k-tuples U i1 , . . . , U i k are homogeneous: we have that either

If the points of P can be perturbed in a general position, the bound improves to O(1/ǫ d+1 ), and the partition is attained via a single partitioning polynomial (albeit, at expense of a possible increase in the worst-case running time).

The best previously known such partition, due to Fox, Pach and Suk requires Ω n k-1 /ǫ c time and yields K = 1/ǫ c parts (for 0 < ǫ ≤ 1/4), where c is an enormous constant which is not stated explicitly and depends not only on the dimension d but also on the semi-algebraic description complexity of the hypergraph.

In contrast to the previous such regularity lemmas which were established by Fox, Gromov, Lafforgue, Naor, and Pach and, subsequently, Fox, Pach and Suk, our partition of P does not depend on the edge set E, provided its semi-algebraic description complexity does not exceed a certain constant.

As a by-product, we show that in any k-partite k-uniform hypergraph (P 1 ⊎ . . . ⊎ P k , E) of bounded semi-algebraic description complexity in R d and with |E| ≥ ǫ