A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of every k -partite k -uniform semialgebraic hypergraph H = (P-1 U center dot center dot center dot U P-k, E) with vertical bar E vertical bar >= epsilon ll(j=1)(k) vertical bar P-i vertical bar have, for 1