Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ${\mathbb{R}}^d$ into constant-complexity subcells. In…