Dynamic Nearest-Neighbor Searching Under General Metrics in ${ℝ}^{\mathrm{𝟑}}$ and Its Applications

Let $K$ be a compact, centrally-symmetric, strictly-convex region in ${ℝ}^3$, which is a semi-algebraic set of constant complexity.¹¹1Roughly speaking, a semi-algebraic set in ${ℝ}^d$ is the set of points in ${ℝ}^d$ that satisfy a Boolean formula over a set of polynomial inequalities; the complexity of a semi-algebraic set is the number of polynomials defining the set and their maximum degree. See [12] for formal definitions of a semi-algebraic set and its complexity. $K$ is the unit ball of a norm $\parallel \cdot {\parallel }_K$, and we denote its metric as ${\mathrm{dist}}_K$.

A homothet (or homothetic copy) of $K$ is a scaled and translated copy of $K$, expressed as $K(c,\rho ):=\rho K+c$, for $c\in {ℝ}^3$ and $\rho \ge 0$; $c$ is the center of $K(c,\rho )$ and $\rho$ is its size. We represent $K(c,\rho )$ as the point $(c,\rho )\in {ℝ}^3\times {ℝ}_{\ge 0}$. Let $𝕂$ be the set of all homothets of $K$, represented as the halfspace $x_4\ge 0$ of ${ℝ}^4$. The $K$-distance ${\mathrm{dist}}_K(u,v)={\Vert u-v\Vert }_K$ between points $u,v\in {ℝ}^3$ is the minimum value of $\rho$ for which $v\in K(u,\rho )$ (or, equivalently, $u\in K(v,\rho )$). Since $K$ is strictly convex, the triangle inequality ${\mathrm{dist}}_K(u,v)\le {\mathrm{dist}}_K(u,w)+{\mathrm{dist}}_K(w,v)$ is sharp unless $w$ lies on the segment $uv$. The $K$-distance of a point $x\in {ℝ}^3$ from a homothet $K(c,\rho )$ is defined as $f_{c,\rho }(x)={\mathrm{dist}}_K(c,x)-\rho$, and the $K$ distance of another homothet $K(c^{\prime },{\rho }^{\prime })$ from $K(c,\rho )$ is $f_{c,\rho }(c^{\prime })-{\rho }^{\prime }={\mathrm{dist}}_K(c,c^{\prime })-\rho -{\rho }^{\prime }$. Since $K$ is a constant-complexity semi-algebraic set, $f_{c,\rho }$ is a semi-algebraic function of constant complexity. The homothets $K(c,\rho )$ and $K(c^{\prime },{\rho }^{\prime })$ intersect if the distance between them is non-positive, i.e., ${\mathrm{dist}}_K(c,c^{\prime })\le \rho +{\rho }^{\prime }$, or equivalently, the point $(c^{\prime },{\rho }^{\prime })$ lies above the graph of $f_{c,\rho }$ in ${ℝ}^4$, or vice-versa.

Let $𝒦=\{K_1,\mathrm{\dots },K_n\}\subset 𝕂$ be a set of $n$ homothets of $K$, where $K_i=K(c_i,{\rho }_i)$. In this paper we study two classes of proximity problems related to $𝒦$.

Proximity queries.

We wish to preprocess $𝒦$ into a data structure so that various proximity queries for a query homothet $K_0$, such as intersection-detection (determine whether $K_0$ intersects any homothet of $𝒦$; if the answer is yes, return one such intersecting homothet of $𝒦$), intersection reporting (report all homothets of $𝒦$ that intersect $K_0$), and nearest-neighbor queries (report the homothet of $𝒦$ at the minimum $K$-distance from $K_0$), can be performed efficiently. In addition, the data structure should support insertions and deletions of homothets of $K$.

Searching in the intersection graph and related problems.

Let $𝒢(𝒦)$ denote the intersection graph of $𝒦$, whose vertices are the homothets of $𝒦$ and $(K_i,K_j)$ is an edge if $K_i\cap K_j\ne \mathrm{\varnothing }$. Similarly, for a threshold parameter $r_0$, the $r_0$-proximity graph ${𝒢}_{r_0}(𝒦)$ of $𝒦$ consists of those edges $(K_i,K_j)$ for which ${\mathrm{dist}}_K(K_i,K_j)\le r_0$. We study efficient implementation of graph-search problems on $𝒢(𝒦)$, like BFS or DFS. We also study the reverse shortest path (RSP) problem on $𝒦$: given two elements $K_i,K_j\in 𝒦$ and a parameter , compute the smallest value $r^{\ast }$ for which ${𝒢}_{r^{\ast }}(𝒦)$ contains a path from $K_i$ to $K_j$ with at most $k$ edges.

There is extensive work on nearest-neighbor (NN) searching in many different fields including computational geometry, database systems, and machine learning. We refer the readers to various survey papers [4, 10, 20] for a general overview of known results on this topic. Here we briefly mention a few results that are most closely related to the problems studied in this paper. Agarwal and Matoušek [9] presented a dynamic NN data structure for a point set in ${ℝ}^d$, under the Euclidean metric, that answers a query in $O^{\ast }(n/s^{\varphi })$ time, where $\varphi =1-\frac{1}{\lceil d/2\rceil }$ and $s\in [n,n^{\lceil d/2\rceil }]$ is a storage parameter, using $O^{\ast }(s)$ space and preprocessing; the (amortized) update time for insertions/deletions of points is $O^{\ast }(s/n)$. The bounds were slightly improved – $n^{\epsilon }$ factors were replaced by ${\log }^{O(1)}n$ factors – in [15, 26]. Kaplan et al. [26] presented a dynamic NN data structure for a set $S$ of points in ${ℝ}^2$ under fairly general distance functions. Its performance depends on the complexity of the Voronoi diagram of $S$ under that distance function. For the Minkowski metric induced by a centrally-symmetric convex region, which is a semi-algebraic set of constant complexity, their data structure can answer an NN query in $O({\log }^{2}n)$ time, and handle insertion and deletion of a point in $O(\beta (n){\log }^{5}n)$ and $O(\beta (n){\log }^{9}n)$ amortized expected time, respectively, where $\beta (n)$, a variant of inverse Ackermann’s function, is an extremely slowly growing function; see also [31] for slightly improved bounds. These data structures, however, do not extend to ${ℝ}^3$.

The problem of NN searching under general distance functions in ${ℝ}^3$ is much less understood. By reducing NN queries to ball-intersection queries [8] and using semi-algebraic range-searching data structures [2, 33, 1], an NN query amid the set $𝒦$ of $n$ homothets in ${ℝ}^3$, as above, can be answered in $O^{\ast }(1)$ time using $O^{\ast }(n^4)$ space and preprocessing, or in $O^{\ast }(n^{3/4})$ time using $O(n)$ space and preprocessing. Using recent standard techniques (see, e.g., the Appendix in [1]), one can obtain a space/query-time trade-off, as well as handle insertions/deletions of objects. Using a recent result by Agarwal et al. [5] on the vertical decomposition of the lower envelope of trivariate functions, an NN query amid $𝒦$ can be answered in $O({\log }^{2}n)$ time using only $O^{\ast }(n^3)$ space, but this data structure does not support efficient deletions (insertions can be handled in a standard manner, using the dynamization technique of Bentley and Saxe [13]). Furthermore, it was not known whether an NN query amid $𝒦$ can be answered in $O^{\ast }(n^{2/3})$ time using $O^{\ast }(n)$ space.

Motivated by numerous applications, there has been work on developing fast algorithms for intersection and proximity graphs of $n$ geometric objects. Although the intersection graph may have $\mathrm{\Theta }(n^2)$ edges, the goal in this line of work is to develop algorithms, by exploiting the underlying geometry, that run in $O^{\ast }(n)$ time (or at least in subquadratic time). Cabello and Jejčič [14], and subsequently Chan and Skrepetos [21], presented $O(n\log n)$ implementations of BFS in unit-disk intersection graphs, which was recently extended to general disk-intersection graphs by de Berg and Cabello [22]; see also [25, 26, 29]. The algorithm in [22] can also perform DFS and Dijkstra’s algorithm in $O(n\log n)$ time. Katz et al. [28] showed that BFS in ball-intersection graphs (for congruent or arbitrary Euclidean balls) can be implemented in $O^{\ast }(n^{2\varphi /(\varphi +1)})$ time, where $\varphi =\lfloor d/2\rfloor +1$, so in $O^{\ast }(n^{4/3})$ time for $d=3$. The problem of devising efficient implementations for BFS/DFS in more general graphs in the plane also has received some attention, see, e.g., [6, 7, 27].

The reverse shortest path (RSP) problem for unit disks was studied by Wang and Zhao [36], who gave an $O^{\ast }(n^{5/4})$-time solution. Kaplan et al. [25] improved the runtime to $O^{\ast }(n^{6/5})$ using the shrink-and-bifurcate technique (see [11]), and it was recently improved to $O^{\ast }(n^{9/8})$ by Chan and Huang [17]. The best-known RSP algorithm for arbitrary disks runs in $O^{\ast }(n^{6/5})$ expected time. Katz et al. [28] presented RSP algorithms for balls in ${ℝ}^3$ – with $O^{\ast }(n^{29/21})$ time for congruent balls and $O^{\ast }(n^{56/39})$ for arbitrary balls. The RSP problem also has been studied for other geometric objects in ${ℝ}^2$ [7, 28, 17].

Our main result is a dynamic data structure for answering intersection and NN queries with a homothet of $𝕂$ amid the set $𝒦$ of homothets:

Plugging Theorem 1 into Eppstein’s technique [23], or its enhancement by Chan [16], for maintaining bichromatic closest pairs, using $s=n^{3/2}$, we obtain:

Theorem 1 is obtained by presenting two data structures. The first one (see Section 4.1) uses $O^{\ast }(n^3)$ space, answers a query in $O^{\ast }(1)$ time, and handles an insertion/deletion in $O^{\ast }(n^2)$ amortized expected time. (The data structure in [5] also obtains a similar space/query-time bound but it cannot handle deletions efficiently.) This data structure is based on constructing vertical shallow cuttings, a notion originally introduced in [18, 15], of the graphs of the distance functions of $𝒦$. Roughly speaking, for a parameter $t\ge 1$, a vertical $(n/t)$-shallow cutting of $𝒦$ is a collection of pairwise openly disjoint semi-unbounded pseudo-prisms that covers the region lying below the $k$-level of the arrangement of $𝒦$, where each prism, consisting of all points that lie vertically below a constant-complexity semi-algebraic $3$-dimensional region, intersects the graphs of only $O(n/t)$ functions of $𝒦$. The random-sampling based technique used in [15, 26] to construct a vertical shallow cutting does not immediately extend to our setting because one needs to decompose the $q$-level, for some parameter $q>0$, in the 4D arrangement of the distance functions of $𝒦$ into $O^{\ast }(n^3(q+1))$ constant-complexity cells. Although a recent result [5] constructs such a decomposition of the $0$-level (with $O^{\ast }(n^3)$ cells), it does not extend to larger values of $q$. This problem remains elusive for arrangements of arbitrary trivariate semi-algebraic functions of constant complexity, but we develop a desired decomposition technique for our setting (in Section 2) by exploiting the structural geometric properties of the distance functions of $𝒦$. This result is one of the main technical contributions of the paper. Using our result on the decomposition of the $q$-level, we construct a vertical $(n/t)$-shallow cutting of $𝒦$ of size $O^{\ast }(t^3)$, for any $t$ (Section 3).

The second data structure is a linear-size partition tree, with $O^{\ast }(n^{2/3})$ query time, constructed on the point set ${𝒦}^{\ast }=\{(c_i,{\rho }_i)\mid 1\le i\le n\}\subset {ℝ}^4$, that answers intersection-detection queries on $𝒦$ with a homothet of $𝕂$ as a query. The main technical challenge we face here is the construction of a so-called test set of $𝒦$ (see [35] and below) of size $r^{O(1)}$, which represents well the distance functions of all $(n/r)$-shallow homothets in $𝕂$, i.e., the homothets that intersect at most $n/r$ elements of $𝒦$. By adapting the technique in [35] and again exploiting the structural geometric properties of the distance functions, we show that a test set, of size $O^{\ast }(r^4)$, with the desired properties can be constructed efficiently.

Using Theorem 1 and Corollary 2, we obtain our second set of results:

Combining Theorem 3(a) with the shrink-and-bifurcate technique [11, 25] yields:

Because of lack of space, the proofs of Theorems 3 and 4 and of some of the lemmas are omitted from this version.

Let $𝒦=\{K_1,\mathrm{\dots },K_n\}$, where each $K_i$ is a homothetic copy of $K$ represented by a point $K_i^{\ast }=(c_i,{\rho }_i)$ in ${ℝ}^4$. For $1\le i\le n$, set $f_i=f_{c_i,{\rho }_i}$, and let $ℱ:=ℱ(𝒦)=\{f_i\mid 1\le i\le n\}$. (As noted, distances from points $x$ that lie inside some copy $K_i$, still measured by $f_i(x)$, are nonpositive.) We will not distinguish between a function of $ℱ$ and its graph. For a point $x\in {ℝ}^3$, $K_i$ is the nearest neighbor of $x$ in $𝒦$ (under the $K$-distance ${\mathrm{dist}}_K$), i.e., $i=\arg {\min }_{1\le j\le n}{f}_j(x)$, if $f_i$ appears on the lower envelope of $ℱ$ at $x$.

The level of a point $p\in {ℝ}^4$ in $𝒜(ℱ)$ is the number of functions in $ℱ$ whose graphs lie below $p$. For a parameter , the $k$-level of $𝒜(ℱ)$, denoted ${𝒜}_k(ℱ)$, is the (closure of the) locus of all points on $\bigcup ℱ$ whose level is $k$. We define the $(\le k)$-level of $𝒜(ℱ)$, denoted ${𝒜}_{\le k}(ℱ)$, to be the (closure of the) set of all points in ${ℝ}^4$ of level at most $k$, i.e., the set of points that lie on or below ${𝒜}_k(ℱ)$ (not necessarily on $\cup ℱ$). The projection of ${𝒜}_k(ℱ)$ onto ${ℝ}^3$, denoted by ${ℳ}_k={ℳ}_k(𝒦)$, is a subdivision of ${ℝ}^3$. If a cell ${\tau }^{\downarrow }$ of ${ℳ}_k$ is the projection of a cell $\tau$ of ${𝒜}_k(ℱ)$ that lies on the graph of $f_i$, then $K_i$ is the $k$-th nearest neighbor in $𝒦$ (under the $K$-distance function) of all points in ${\tau }^{\downarrow }$. Note that $A_0(ℱ)$ is the lower envelope of $ℱ$, and ${ℳ}_0(𝒦)$ is the Voronoi diagram of $𝒦$ (under the $K$-distance).

The main technical result of this section is that ${𝒜}_k(ℱ)$ can be decomposed into $O^{\ast }(n^3(k+1))$ elementary cells, namely, constant-complexity semi-algebraic regions, each homeomorphic to a ball; see below for a more precise definition.

For $1\le i\ne j\le n$, let $B_{ij}=\{x\in {ℝ}^3\mid f_i(x)=f_j(x)\}$ be the bisector of $K_i$ and $K_j$ under the $K$-distance. Note that if $K_i\subset K_j$ then, as is easily verified, for all $x\in {ℝ}^3$ and $B_{ij}$ is undefined. The following lemma gives a useful property of bisectors.

We are now ready to describe the decomposition of the cells of ${𝒜}_k(ℱ)$ into elementary cells. (Our ultimate goal is to decompose the region below ${𝒜}_k(ℱ)$ into elementary cells, but we start with this subtask.) For $1\le i\le n$, let ${𝒜}_k^i={𝒜}_k^i(ℱ)$ denote the subset of cells of ${𝒜}_k(ℱ)$ that lie on the graph of $f_i$, and let ${ℳ}_k^i$ denote their projections (which are the cells of ${ℳ}_k$ for which $K_i$ is the $k$-th nearest neighbor). We describe the algorithm for decomposing the cells of ${ℳ}_k^i$ (or of ${𝒜}_k^i$). Lemma 5 implies that, for any $j\ne i$, $B_{ij}$ can be viewed as the graph of a function $g_{ij}:{𝕊}^2\to {ℝ}_{\ge 0}$ in spherical coordinates with $c_i$ as the origin. That is, for a given $u\in {𝕊}^2$, let $\lambda (u)$ be the ray emanating from $c_i$ in direction $u$, and let $x_{ij}(u)$ be the intersection point of $\lambda (u)$ with the bisector $B_{ij}$ if such an intersection point exists; otherwise $x_{ij}(u)$ is undefined. We set $g_{ij}(u)=f_j(x_{ij}(u))$ if $x_{ij}(u)$ is defined and $+\mathrm{\infty }$ otherwise. Let $G^{(i)}=\{g_{ij}\mid 1\le j\ne i\le n\}$. We define the level of a point $x\in {ℝ}^3$ in (the 3D arrangement, within ${𝕊}^2\times ℝ$) $𝒜(G^{(i)})$ to be the number of functions in $G^{(i)}$ whose graphs intersect the (relatively open) segment $c_{i}x$. The following lemma will be useful in analyzing the complexity of the decomposition of ${𝒜}_k^i$.

It is obvious from the definition of $G^{(i)}$ that ${\tau }^{\downarrow }$ is a cell in $𝒜(G^{(i)})$. We now argue that its level in $𝒜(G^{(i)})$ is at most $k$. Choose a point $x\in {\tau }^{\downarrow }$. Let $\lambda$ be the ray emanating from $c_i$ and passing through $x$. Let $g_{ij}$ be a function whose graph intersects the segment $c_{i}x$, say, at a point $x_0\in B_{ij}$. (See Fig. 1.) By Lemma 5, for all points $y$ on $\lambda$ preceding $x_0$, and for all points on $\lambda$ beyond $x_0$. In particular, $f_i(x)>f_j(x)$. Since $\tau$ is a cell of $𝒜(ℱ)$, $f_j$ does not intersect $\tau$, so $f_j$ lies below $\tau$ in ${ℝ}^4$ (in the $x_4$-, or rather $\rho$-direction). Furthermore, $\tau \in {𝒜}_k(ℱ)$, so there are exactly $k$ functions of $ℱ$ whose graphs lie below $\tau$, implying that the level of ${\tau }^{\downarrow }$ in $𝒜(G^{(i)})$ is at most $k$, as claimed. $◀$

We decompose the cells $\tau$ of ${𝒜}_k^{(i)}(ℱ)$ by constructing “vertical decompositions” of the corresponding 3D projections ${\tau }^{\downarrow }$ in the spherical coordinate system around $c_i$. As for standard vertical decompositions in 3D, we proceed in two stages. The first stage erects a wall from each edge of $\tau$ as follows. Fix an edge $e$ of ${\tau }^{\downarrow }$. For a point $x\in e$, let $\lambda (x)$ be the ray emanating from $c_i$ and passing through $x$, and let $h(x)=\lambda (x)\cap {\tau }^{\downarrow }$. By Lemma 5, $h(x)$ is a (connected) segment that touches $e$ at one of its endpoints – it is either the top endpoint, for all points on $e$, or the bottom endpoint (with respect to distances from $c_i$). We erect the wall $\widehat{e}={\bigcup }_{x\in e}h(x)$ in ${\tau }^{\downarrow }$; parts of the wall may extend to infinity when ${\tau }^{\downarrow }$ is unbounded and $e$ is a bottom edge. We repeat this step for all edges of ${\tau }^{\downarrow }$. These walls decompose ${\tau }^{\downarrow }$ into frustums (truncated cones), each of which, denoted by $\mathrm{\Delta }$, has a unique pair of front and back faces; the other faces of $\mathrm{\Delta }$ lie on the created walls. (See Fig. 2.) The projections of the front and back faces of $\mathrm{\Delta }$ on ${𝕊}^2$ (with $c_i$ as the origin) are identical, and we denote this identical projection by ${\mathrm{\Delta }}^{\downarrow }$. The complexity of ${\mathrm{\Delta }}^{\downarrow }$ may be arbitrarily large (a typical situation in the first stage of vertical decompositions in general; see, e.g., [19]). The subcell $\mathrm{\Delta }$ itself is of the form $\mathrm{\Delta }=\{(u,r)\mid u\in {\mathrm{\Delta }}^{\downarrow },r\in [g^{-}(u),g^{+}(u)]\}$, where $g^{-},g^{+}$ are the functions of $G^{(i)}$ whose graphs contain the front and back faces of $\mathrm{\Delta }$, respectively.

The second stage decomposes $\mathrm{\Delta }$ into constant-complexity frustums, which we refer to as pseudo-cones. We decompose ${\mathrm{\Delta }}^{\downarrow }$ into spherical pseudo-trapezoids, by drawing portions of meridians within ${\mathrm{\Delta }}^{\downarrow }$ from each vertex and meridian-tangency point. We then lift each pseudo-trapezoid ${\sigma }^{\downarrow }$ to form the pseudo-cone $\sigma =\{(u,r)\mid u\in {\sigma }^{\downarrow },r\in [g^{-}(u),g^{+}(u)]\}$ in ${ℝ}^3$.

Repeating this step for all frustums created in the first stage, we obtain a decomposition of ${\tau }^{\downarrow }$ into pseudo-cones, each being a semi-algebraic set of constant complexity and bounded by up to six facets (compare with standard vertical decompositions in 3D [19]). We refer to these pseudo-cones as elementary cells. We note that each pseudo-cone $\varphi$ is defined by a subset $D_{\varphi }$ of at most seven functions of $ℱ$ (the function $f_i$ and up to six additional functions that define the functions $g_{ij}$ that form the frustum), in the sense that $\varphi$ appears in the vertical decomposition of a 3D cell of $𝒜(D_{\varphi })$. By repeating this step for all cells of ${ℳ}_k^i$ and for all homothets $K_i$ of $𝒦$, we obtain a decomposition of ${ℳ}_k={ℳ}_k(𝒦)$ into elementary cells. Finally, we lift each elementary cell of this decomposition vertically to ${𝒜}_k(ℱ)$ in a straightforward manner, to obtain a corresponding decomposition of ${𝒜}_k(ℱ)$.

Kaplan et al. [26, Lemma 6.2] have shown that the complexity of the vertical decomposition of the $(\le k)$-level ${𝒜}_{\le k}(𝒢)$ of a set of $𝒢$ of $m$ bivariate semi-algebraic functions of constant complexity is $O(k^2\psi (n/k){\lambda }_s(k))$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of $𝒢$ of size at most $r$, ${\lambda }_s(t)$ is the maximum length of Davenport-Schnizel sequences of order $s$ composed of $t$ symbols [34], and $s$ is a constant depending on the complexity of the functions in $𝒢$. By applying the argument in [26] to our spherical coordinate system and using the worst-case bound $\psi (m)=O^{\ast }(m^2)$ on the complexity of the lower envelope of $m$ constant-complexity bivariate functions [34], we conclude that the cells of ${ℳ}_k^i$ can be decomposed into $O^{\ast }(n^{2}k)$ elementary cells. Hence, ${𝒜}_k(ℱ)$, or ${ℳ}_k(𝒦)$, can be decomposed into $O^{\ast }(n^{3}k)$ elementary cells. By adapting the randomized incremental algorithm described in [26], ${ℳ}_k^i$, for each $i$, can be computed in $O^{\ast }(n^{2}k)$ expected time. We thus obtain:

Let $\mathrm{\Sigma }=(𝖷,ℛ)$ be a (finite) range space, where $𝖷$ is a set of objects and $ℛ\subseteq 2^{𝖷}$ a set of ranges. Let be a given parameter. A subset $𝖭\subseteq 𝖷$ is called a shallow $\epsilon$-net of $\mathrm{\Sigma }$ if it satisfies the following two properties for every range $R\in ℛ$ and for any parameter $\zeta \ge 0$:

1. (i)

   If $|R\cap 𝖭|\le \zeta \log \frac{1}{\epsilon }$ then $|R\cap 𝖷|\le \alpha (\zeta +1)\epsilon |𝖷|$, and

2. (ii)

   If $|R\cap 𝖷|\le \zeta \epsilon |𝖷|$ then $|R\cap 𝖭|\le \alpha (\zeta +1)\log \frac{1}{\epsilon }$.

Here $\alpha$ is a suitable constant. Note the difference between shallow and standard $\epsilon$-nets: Property (i) (with $\zeta =0$) implies that a shallow $\epsilon$-net is also a standard $\epsilon$-net (possibly with a recalibration of $\epsilon$). Property (ii) has no parallel in the case of standard $\epsilon$-nets – there is no guarantee how a standard net interacts with small ranges (of the entire set $𝖷$). The following result by Sharir and Shaul [35] is a generalization of the result on standard $\epsilon$-nets [24].

We apply the above result to the range space $\mathrm{\Sigma }=(ℱ,ℛ)$, so that each range in $ℛ$ is the subset of the surfaces of $ℱ$ that cross some region in ${ℝ}^4$, taken from some family $\mathrm{\Gamma }$ of regions. Concretely, this includes the following families $\mathrm{\Gamma }$: (i) the set of pseudo-cones generated by the decomposition of a set of at most seven functions of $ℱ$ (recall that a pseudo-cone is defined by at most seven functions), (ii) the set of pseudo-prisms erected on these pseudo-cones, (iii) the set of edges in an arrangement of five functions of $ℱ$ (an edge in the arrangement of a subset of $ℱ$ is defined by at most five functions), and (iv) the set of rays in the positive $x_4$-direction. Using standard arguments, it can be shown that the VC-dimension of $\mathrm{\Sigma }$ is finite. Therefore, by applying Lemma 8 with $\epsilon =1/t$ and $\delta =1/3$ and choosing the constant of proportionality appropriately, the random subset $ℛ$ is a $(1/t)$-shallow net of $\mathrm{\Sigma }$ with probability at least $2/3$, so we assume that $𝖭$ is indeed a $(1/t)$-shallow net of $\mathrm{\Sigma }$. Recall that $q=\beta \log t$. Assuming $\beta \ge 2\alpha$, where $\alpha$ is the constant in the definition of shallow nets, the converse of property (ii) of shallow nets, with $\zeta =1$, implies that the level of any point $p$ on ${𝒜}_q(𝖭)$ with respect to $ℱ$ is at least $n/t$. Also, by property (i), the level of $p$ is at most $O(n/t)$. Finally, the shallow net property also implies that the size of the conflict-list of any prism in ${\mathrm{\Xi }}^{\uparrow }$ is $O(n/t)$. The conflict list of all prisms can be computed in $O^{\ast }(n{t}^3)$ time. Hence, we obtain: