  We provide polynomial upper bounds for the minimal sizes of distal cell
decompositions in several kinds of distal structures, particularly weakly
$o$-minimal and $P$-minimal structures. The bound in general weakly $o$-minimal
structures generalizes the vertical cell decomposition for semialgebraic sets,
and the bounds for vector spaces in both $o$-minimal and $p$-adic cases are
tight. We apply these bounds to Zarankiewicz's problem and sum-product bounds
in distal structures.

Logic;Combinatorics