2023/11/02 by Pankaj K. Agarwal, Agarwal, Pankaj K., Esther Ezra +3
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2311.01597
openalex publication_date 2023/11/02 · openalex created_date 2023/11/07 · openalex updated_date 2026/07/28
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 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 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 4D lying below the lower envelope of F is O^*(n3). 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.