  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 paper, we settle in the affirmative a few
long-standing open problems involving the vertical decomposition of
substructures of arrangements for $d=3,4$: (i) Let $\mathcal{S}$ be a
collection of $n$ semi-algebraic sets of constant complexity in 3D, and let
$U(m)$ be an upper bound on the complexity of the union
$\mathcal{U}(\mathcal{S}')$ of any subset $\mathcal{S}'\subseteq \mathcal{S}$
of size at most $m$. We prove that the complexity of the vertical decomposition
of the complement of $\mathcal{U}(\mathcal{S})$ is $O^*(n^2+U(n))$ (where the
$O^*(\cdot)$ notation hides subpolynomial factors). We also show that the
complexity of the vertical decomposition of the entire arrangement
$\mathcal{A}(\mathcal{S})$ is $O^*(n^2+X)$, where $X$ is the number of vertices
in $\mathcal{A}(\mathcal{S})$. (ii) Let $\mathcal{F}$ be a collection of $n$
trivariate functions whose graphs are semi-algebraic sets of constant
complexity. We show that the complexity of the vertical decomposition of the
portion of the arrangement $\mathcal{A}(\mathcal{F})$ in 4D lying below the
lower envelope of $\mathcal{F}$ is $O^*(n^3)$.
  These results lead to efficient algorithms for a variety of problems
involving these decompositions, including algorithms for constructing the
decompositions themselves, and for constructing $(1/r)$-cuttings of
substructures of arrangements of the kinds considered above. One additional
algorithm of interest is for output-sensitive point enclosure queries amid
semi-algebraic sets in three or four dimensions. In addition, as a main domain
of applications, we study various proximity problems involving points and lines
in 3D.
