Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D
Pankaj K. Agarwal, Esther E. Ezra, Micha Sharir · Society for Industrial and Applied Mathematics eBooks · 2024
Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ℝd 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 S be a collection of n semi-algebraic sets of constant complexity in ℝ3, and let U(m) be an upper bound on the complexity of the union U(S‘) of any subset S’ ⊆ S of size at most m. We prove that the complexity of the vertical decomposition of the complement of U(S) is O* (n2 + U(n)) (where the O* (·) notation hides subpolynomial factors). We also show that the complexity of the vertical decomposition of the entire arrangement A(S) is O*(n2 + X), where X is the number of vertices in A(S). (ii) Let 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 A(F) in ℝ4 lying below the lower envelope of F is O*(n3).