English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Vertical decomposition is a widely used general technique for decomposing thecells of arrangements of semi-algebraic sets in $d$-space intoconstant-complexity subcells. In this paper, we settle in the affirmative a fewlong-standing open problems involving the vertical decomposition ofsubstructures of arrangements for $d=3,4$: (i) Let $\mathcal{S}$ be acollection 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 decompositionof 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 thecomplexity of the vertical decomposition of the entire arrangement$\mathcal{A}(\mathcal{S})$ is $O^*(n^2+X)$, where $X$ is the number of verticesin $\mathcal{A}(\mathcal{S})$. (ii) Let $\mathcal{F}$ be a collection of $n$trivariate functions whose graphs are semi-algebraic sets of constantcomplexity. We show that the complexity of the vertical decomposition of theportion of the arrangement $\mathcal{A}(\mathcal{F})$ in 4D lying below thelower envelope of $\mathcal{F}$ is $O^*(n^3)$.  These results lead to efficient algorithms for a variety of problemsinvolving these decompositions, including algorithms for constructing thedecompositions themselves, and for constructing $(1/r)$-cuttings ofsubstructures of arrangements of the kinds considered above. One additionalalgorithm of interest is for output-sensitive point enclosure queries amidsemi-algebraic sets in three or four dimensions. In addition, as a main domainof applications, we study various proximity problems involving points and linesin 3D.

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