Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D

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 $d$-space into constant-complexity subcells. In this p…