Incremental $k$-Lowest Planes and Planar $k$-Nearest Neighbor with Optimal Query Time

Our main result is the insertion-only data structure that answers $k$-lowest planes queries in optimal time $O(\log n+k)$. This data structure can be used to obtain optimal query time for several semi-dynamic and static problems. Henceforth we use $n$ to denote the number of geometric objects (points, planes) stored in the data structure and we use $k$ to denote the number of geometric objects that are reported when we answer a query.

1. 1.

   Vertical ray shooting in a set of 3D planes. A vertical ray shooting query $q$, for a three-dimensional point $q$, asks for all planes that are pierced by the downward vertical ray from $q$. We obtain a semi-dynamic insertion-only data structure that answers vertical ray shooting queries in $O(\log n+k)$ time.

2. 2.

   Halfspace range reporting in a set of 3D points. A halfspace range reporting query $h$ asks for all points that are below a plane $h$. We obtain a semi-dynamic insertion-only data structure that answers halfspace range reporting queries in $O(\log n+k)$ time.

3. 3.

   Nearest neighbor in a set of planar points. A nearest neighbor query $q$, for a two-dimensional point $q$, asks for the point that is closest to $q$. A $k$-nearest neighbor query $(q,k)$, for a point $q$ and integer $k\ge 1$, asks for $k$ points that are closest to $q$. We describe a semi-dynamic insertion-only data structure that answers $k$-nearest neighbor queries in $O(\log n+k)$ time for any $k$; integer $k$ can be specified at query time.

4. 4.

   Circular range reporting in a set of planar points. A circular range reporting query $(q,R)$ asks for all points in the circle with center $q$ and radius $R$. We obtain a semi-dynamic insertion-only data structure that answers circular range reporting queries in $O(\log n+k)$ time.

5. 5.

   Weighted halfspace range reporting. In this generalization of halfspace reporting, each 3D point has an additional coordinate called weight. A weighted halfspace reporting query $(h,w_1,w_2)$, for a 3D plane $h$ and reals $w_1$ and $w_2$, asks for all points that are below $h$ and have weight within $[w_1,w_2]$. We describe a static data structure that answers weighted halfspace reporting queries in $O(\log n+k)$ time.
   (This result is somewhat unexpected because weighted halfspace reporting is a 4D problem. For comparison, the fastest currently known data structure for orthogonal range reporting in 4D answers queries in $O(\log n\log \log n+k)$ time in the pointer machine model [22].)

All semi-dynamic data structures use $O(n)$ space and support insertions in $O({\log }^{8}n)$ amortized time. Our static structure for weighted halfspace reporting uses $O(n{\log }^{9}n)$ space.

The complexity of the $k$-lowest planes problem, and almost all its applications that we consider in this paper, are well understood in static scenarios. If $k$ is fixed at preprocessing time, we can work with the $k$-level of the set of planes. The $k$-level of a set of $n$ planes is a polyhedral terrain of complexity $O(n\cdot k^{3/2})$ [23]. The fastest known deterministic construction takes $O(n\log n+n{k}^{3/2})$ time [8]. In order to answer the $k$-lowest planes query it is sufficient to find the face of the $k$-level that is pierced by $q$, which can be solved in $O(\log n)$ time. If $k$ is prescribed at query time, state-of-the-art solutions are based on a hierarchy of $k_i$-shallow cuttings with values $k_i$ that form a geometric series. Chan and Tsakalidis [9] showed that such a hierarchy can be computed in $O(n\log n)$ deterministic time, which yields a simple data structure with $O(\log n+k)$ query time. The space bound of this approach can be made $O(n)$, while retaining the query bound, using 3D halfspace range reporting queries from the (recursive) structure of Afshani and Chan [1], which was derandomized in [9].

Halfspace range reporting with $O(\log n+k)$ query time and $\mathrm{polylog}(n)$ updates is only known for 2D, which degrades to $O({\log }^{2}n/\log \log n+k)$ query time in 3D [6, Section 3], since interval trees and fractional cascading do not generalize [11].

For weighted halfspace reporting, one can use a range tree on the weights of points to obtain a data structure with $O(n\log n)$ space and $O({\log }^{2}n+k)$ query time. Since this variant of halfspace reporting is a 4D problem, this query time appears to be close to optimal. However, the very recent data structure of Afshani et al. [2] supports weighted halfspace reporting queries in $O({\log }^{3/2}n+k)$ time, for a given query plane $h$ and weight range $[w_1,w_2]$.

If insertions and deletions are required, one can answer $1$-nearest neighbor queries in $O({\log }^{2}n)$ time with polylogarithmic updates [7]. In [13] de Berg and Staals extended this result to $k$-nearest neighbor and obtained a data structure with $O({\log }^{2}n/\log \log n+k)$ query time. Improving the query time of these works is challenging; most progress has been made on update time [5, 19, 7].

Recently, Iacono and Nekrich [17] described a novel, insertion-only structure that answers $1$-nearest neighbor queries in $O(\log n)$ time with $O({\log }^{1+\epsilon }n)$ amortized insertion time, where $\epsilon >0$ can be made an arbitrary small constant.

This work is inspired by the $O(\log n)$ query time result in [17] for incremental planar $1$-nearest neighbor, that introduced a sampling technique that allows maintaining the optimal $O(\log n)$ query time, with $O({\log }^{1+\epsilon }n)$ amortized insertion cost. However, immediate extension to the incremental $k$-lowest planes problem is quite unclear, already for $k=1$, since the algorithms and correctness arguments heavily rely on Euclidean distances and geometric observations about the Voronoi cells around points.

One contribution of our work is to simplify their approach into a more general framework, that applies to the incremental $k$-lowest planes problem. Specifically, we show in Section 3 that query correctness, and the $O(\log n)$ query time, can be established based on a suitable implicit representation of (sample augmented) sets of planes. This is somehow surprising, as a query may, for example, ask for the $\lceil {\log }^{3/2}n\rceil$-lowest planes in some $q$. In obtaining the explicit answer of the reporting query, we are tackling the difficulty that our technique, which gives the speedup, prevents direct access to the known Heap-Selection techniques from [13, 15, 18]. To solve this, we introduce a Deduplication Lemma in Subsection 3.1 for such sampling techniques, which allows us to obtain the optimal $O(\log n+k)$ query time.

Our Section 4 shows how to reduce space to $O(n)$, which we believe is of general interest for several dynamic problems (beside $k$-lowest planes). Section 5 shows how to obtain the first optimal bounds for aforementioned applications 1-5 from our proposed method.

We see the obtained generalization to the $k$-lowest problem and the Deduplication Lemma as the main technical contributions of this work. Furthermore, our proofs in Section 3 proceed in three abstract steps (i) query correctness, (ii) construction time, and (iii) query runtime, which makes our framework easily accessible for future work on optimal query time.

Though our $O({\log }^{8}n)$ insertion bound for the $k$-lowest planes problem is considerably larger than the almost logarithmic bound for planar $1$-nearest neighbor from [17], we believe that it is very challenging to improve the insertion bound to a sub-cubic exponent (see proof of Lemma 5). While it is an interesting technical problem to accelerate our Skip-Decider construction, one barrier would remain. A central obstacle that comes with our approach is the apparent complexity of the $\lceil {\log }^{2}n\rceil$-level of a set of $n$ planes, where the best known bound $O(n{\log }^{3}n)$ remained unchanged for decades [23].

The new optimal bounds improve the state-of-the-art for fundamental problems planar $k$-nearest-neighbor [13], 3D halfspace reporting [6, 7], and weighted halfspace reporting [2].

As it turns out for the $\overline{k}$-lowest planes problem, the structures obtained from algorithm CONSTRUCT in Lemma 5 will allow performing one greedy-step, from $i$ to $i^{\prime }$, in $(i^{\prime }-i)O(\log d)$ time (cf. Lemmas 6 and 7). That is, the total query time then telescopes to optimal

time, regardless of the number $m$ of greedy-steps. With respect to the $\overline{k}$-lowest planes problem, the proposed greedy trial-and-error approach for queries can be described concisely with the pseudo-code in Figure 2.

A naïve implementation for the post-processing PRUNE$(k,\mathrm{\dots })$ runs in $O(\overline{k}{\log }_{d}N)$ time, since each of $O({\log }_{d}N)$ triangles in the sequence has $\overline{k}$ elements in $H(\mathrm{\Delta })$.

In the following lemma, we define the semantics of SKIP$(\mathrm{\Delta },q,\mathrm{\ell })$ and what an evaluation to True implies for $\overline{k}$-lowest$(q,{\widehat{H}}_i\cup \mathrm{\dots }\cup {\widehat{H}}_{i+\mathrm{\ell }})$. After this, Lemma 4 will then discuss the semantic of FIX and what “tentative result” and “correct for a prefix” means. Discussion of how quickly SKIP and FIX can be computed with suitable data structures is carried out in Lemmas 5, 6, and 7.

We call degenerate triangles just triangles in the following, as the arguments will hold regardless of corner count. It suffices to show for arbitrary $j>i$, that

Since $\mathrm{\Delta }\in D_i$ is the triangle that intersects vertical line $q$, we have $\overline{k}$-lowest$(q,{\widehat{H}}_i)=H(\mathrm{\Delta })$. See Figure 3.

Consider the set of points on the polyhedral surface $A\subseteq L(\overline{k},{\widehat{H}}_i\cup {\widehat{H}}_j)$ where the $\overline{k}$-lowest planes coincide with $H(\mathrm{\Delta })$. Let $A^{\ast }\subseteq {ℝ}^2$ be the orthogonal projection of $A$. (In other words, the region of queries that may be skipped as their set of $\overline{k}$-lowest planes is equal to $H(\mathrm{\Delta })$.) The implication (3) follows, if we can show that $\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_j)\subseteq A^{\ast }$ is true.

If $\mathrm{\Delta }\cap S_j=\mathrm{\varnothing }$, then $\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_j)=\mathrm{\varnothing }$ and the implication is true²²2In other words, SKIP returns False in this case.. So let $q^{\prime }\in \mathrm{\Delta }\cap S_j$ be arbitrary. Since $q^{\prime }\in {\mathrm{\Delta }}^{\prime }$ of some ${\mathrm{\Delta }}^{\prime }\in {\mathrm{𝖲𝖬𝖯𝖫}}_j(j-i)$, we have $\overline{k}$-lowest$(q^{\prime },{\widehat{H}}_j)=H({\mathrm{\Delta }}^{\prime })$ are in the augmented set, i.e. $H({\mathrm{\Delta }}^{\prime })\subseteq {\widehat{H}}_i\setminus H_i$. From $q^{\prime }\in \mathrm{\Delta }$, we have that $\overline{k}$-lowest$(q^{\prime },{\widehat{H}}_i)=H(\mathrm{\Delta })$. Thus, $q^{\prime }\in A^{\ast }$ and $A^{\ast }\ne \mathrm{\varnothing }\ne A$.

The lemma now follows from $A^{\ast }$ being convex, due to $A$ being convex (Lemma 1).$◀$

In the following, we define the necessary semantic of FIX, “tentative result”, and “correct for a prefix”, which allows us to establish the correctness of our greedy trial-and-error approach for the $\overline{k}$-lowest planes problem. Establishing runtime efficiency, with suitable data structures, is carried out in Lemmas 5, 6, and 7.

The proof is by induction. The prefix invariant holds for $[0,i]$ for some $i\ge 0$, since the query algorithm always determines the intersected triangle in $D_i$ with minimal index $i$ in the BS partition as the first triangle in a tentative result. Let $\mathrm{\Delta }\in D_i$ be the last triangle in the sequence that is valid for $[0,i]$. Apply Lemma 2, and use that $i^{\prime }$ is minimal, and ${\mathrm{\Delta }}^{\prime }\in D_{i^{\prime }}$ with $q\cap {\mathrm{\Delta }}^{\prime }\ne \mathrm{\varnothing }$, so true for $[0,i^{\prime }]$. $◀$

Next, we discuss the algorithm $\mathrm{𝖢𝖮𝖭𝖲𝖳𝖱𝖴𝖢𝖳}$ for computing ${\widehat{H}}_i$ and its associated triangulation $D_i$, including how the triangles ${\mathrm{𝖲𝖬𝖯𝖫}}_i(j)\subseteq D_i$ are obtained for all possible integers $j\in [1,i]$, and the three kinds of planar point-location structures associated to $D_i$ that we will need to establish that $\mathrm{𝖲𝖪𝖨𝖯}$ and $\mathrm{𝖥𝖨𝖷}$ can be computed sufficiently fast during queries.

We first assemble $H_i$ by merging the old prefix sets ${\bigcup }_{\mathrm{\ell }\le i}{H}_{\mathrm{\ell }}$ from the partition, drop all structures related to the old prefix sets, and then add all planes from the sampled triangles from higher indices to obtain the augmented set

Then we compute $\overline{k}$-level $L(\overline{k},{\widehat{H}}_i)$, project its faces into the plane, and compute its triangulation $D_i$, which takes $O(|{\widehat{H}}_i|{\log }^{3}N)$ deterministic time, since $\overline{k}=O({\log }^{2}N)$.

We will show that the size of the augmented set remains of the same order $|{\widehat{H}}_i|=O(|H_i|)$, by showing that $\overline{k}|{\mathrm{𝖲𝖬𝖯𝖫}}_{\mathrm{\ell }}(\mathrm{\ell }-i)|$ is sufficiently small in the following.

The number of triangles in the triangulation is at most $|D_i|=O(|{\widehat{H}}_i|{\overline{k}}^{3/2})$, i.e. bounding the nodes in its planar face-adjacency graph (cf. Section 2). Next, we compute a triangle subset ${\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })$ from the face-adjacency graph for each integer $\mathrm{\ell }\in [1,i]$. That is, we compute in linear time a planar-separator ${\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })\subseteq D_i$ such that each connected component of $D_i\setminus {\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })$ contains $\le r_{\mathrm{\ell }}:=d^{16+2\mathrm{\ell }}$ triangles, is adjacent to $O(d^{8+\mathrm{\ell }})$ triangles from the separator, and contains a number of triangles that is at most $|{\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })|\le O(|D_i|/d^{8+\mathrm{\ell }})$. Note that invocations with $r_{\mathrm{\ell }}\ge |D_i|$ are trivial, as this yields one connected component containing all nodes and empty separator ${\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })=\mathrm{\varnothing }$. (E.g. any skip-range containing such an empty ${\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })$ evaluates to False.)

To show the claimed $|{\widehat{H}}_i|=O(|H_i|)$, we first consider the right-most BS set ($i=f$), where $H_f={\widehat{H}}_f$ and $|H_f|=N=O(d^f)$ holds.

Since $|D_f|=O(|H_f|{\overline{k}}^{3/2})=O(N{\log }^{3}N)$, the number of planes in the down-samples at index distance $\mathrm{\ell }$ is $\overline{k}|{\mathrm{𝖲𝖬𝖯𝖫}}_f(\mathrm{\ell })|=O(N{d}^5/d^{8+\mathrm{\ell }})$.

Thus, $|{\widehat{H}}_{f-1}|\le |H_{f-1}|(1+\frac{O(|H_f|d^5/d^{8+1})}{|H_{f-1}|})\le |H_{f-1}|(1+\frac{O(d^{f+5-9})}{d^{f-1}})=O(|H_{f-1}|)$.

Using this, we have for $|{\widehat{H}}_{f-2}|\le |H_{f-2}|(1+\frac{O(|{\widehat{H}}_{f-1}|d^{5-(8+1)})+O(|H_f|d^{5-(8+2)})}{d^{f-2}})$, that $|{\widehat{H}}_{f-2}|\le |H_{f-2}|(1+\frac{O(d^{f+5-9})+O(d^{f+5-10})}{d^{f-2}})$. Thus, $|{\widehat{H}}_{f-2}|=O(|H_{f-2}|)$. Consequently,

That is, $|D_i|=O(|H_i|{\overline{k}}^{3/2})$, as claimed.

The planar separator algorithm takes linear $O(|D_i|)$ time for one execution, and is executed $\mathrm{\ell }\le i=O(f)$ times. Thus computing the samples takes $O(f|D_i|)$ total time, also bounding the space for storing the obtained triangle subsets $\{{\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })\subseteq D_i\}$.

Computing a planar point-location structure for triangulation $D_i$ takes $O(|D_i|\log N)$ time and occupies $O(|D_i|)$ space.

For each corner $p$ of a $\mathrm{\Delta }\in D_i$ and each integer $\mathrm{\ell }\in (i,f]$, we perform a global search in $D_{\mathrm{\ell }}$ to determine its containing triangle $\mathrm{\Delta }$, and store the obtained connected component of $\mathrm{\Delta }$ in $D_{\mathrm{\ell }}\setminus {\mathrm{𝖲𝖬𝖯𝖫}}_{\mathrm{\ell }}(\mathrm{\ell }-i)$ with corner $p$. In case $\mathrm{\Delta }$ is a degenerate triangle, two of its boundaries are infinite rays in the plane. There we determine the component membership for the furthest points inside the ray. (Recall that any degenerate triangle is described by two points at infinity and one or two ordinary corner points, and that all standard planar point location structures naturally support queries for a point at infinity specified as ray.) As with a corner point, this also yields either a connected component or a triangle from separator ${\mathrm{𝖲𝖬𝖯𝖫}}_{\mathrm{\ell }}(\mathrm{\ell }-i)$. That is, every $\mathrm{\Delta }\in D_i$ stores at most four pointers to connected components, and locating given point in $D_{\mathrm{\ell }}$ takes $O(\log N)$ time, and determining if found triangle is in the separator ${\mathrm{𝖲𝖬𝖯𝖫}}_{\mathrm{\ell }}(\mathrm{\ell }-i)\subseteq D_{\mathrm{\ell }}$, or the connected component, also takes $O(\log N)$ time. This takes $O(|D_i|f\log N)$ total time and occupies $O(|D_i|f)$ space.

For each integer $\mathrm{\ell }\in [1,i]$ and each connected component of $D_i\setminus {\mathrm{𝖲𝖬𝖯𝖫}}_i(\mathrm{\ell })$, we compute a point-location structure for the triangles in this connected component. This takes $O(|D_i|f\log N)$ total time and occupies $O(|D_i|f)$ space.

For every $\mathrm{\Delta }\in D_i$ and skip-length $2^j\in [1,f-i]$, we compute the planar subdivision that is the overlay of the regions $\{\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{\mathrm{\ell }}):\mathrm{\ell }\in (i,i+2^j]\}$. Note that $j=O(\log f)$. The size is bounded by the number of vertices, so bounded by the total number of vertices in the given convex regions plus the total number of intersection points of edges from the given convex regions. We first bound the total size for fixed $j$. For the first kind, the number of vertices, across all $\mathrm{\Delta }\in D_i$, is already bounded by $O(|D_i|)$ due to the sampling bound above. For the second kind, we consider one $\mathrm{\Delta }\in D_i$. There, any hull edge can intersect only $O(1)$ many edges from another convex hull, and there are $O(2^j)$ many hulls to consider. Let $M_{\mathrm{\Delta }}$ be the complexity of the largest of these hulls within $\mathrm{\Delta }$. Any of these hulls is composed of at most four sections of boundaries of connected-components, referenced by the fix-pointers of $\mathrm{\Delta }$, note that $M_{\mathrm{\Delta }}$ has a worst-case bound of $O(d^{8+2^j})$. (See Figure 4.) Thus, the overlay within $\mathrm{\Delta }$ is a planar subdivision of size $O(2^j{M}_{\mathrm{\Delta }})$. Consequently, the total number of vertices of the second kind is bounded within an $O(2^j)$-factor of ${\sum }_{\mathrm{\Delta }\in D_i}{M}_{\mathrm{\Delta }}$, where the latter sum is bounded by the number of vertices of the first kind. That is, the total size of all overlays for fixed $j$ is $O(2^j|D_i|)$; summing over $j=O(\log f)$ shows that the total space is $O(f|D_i|)$. With the space bound, it follows that the total construction time, for all $\mathrm{\Delta }$ and $j$, is $O(f|D_i|\cdot \log N)$.

Next, we label each face, in the overlay for given $\mathrm{\Delta }$ and $j$. We label (the interior of) each face with the largest integer $i^{\prime \prime }\le i+2^j$ so that its points are contained in each region $(\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i+1}),\mathrm{\dots },\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i^{\prime \prime }}))$. Taking a point $p$ within the face, we determine for $i^{\prime \prime }=i+1,i+2,\mathrm{\dots }$ if $p$ is contained in $\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i^{\prime \prime }})$. This takes $O(\log N)$ time for given point $p$, as discussed for corner point component membership in $D_{i^{\prime \prime }}$ above, and determining $i^{\prime \prime }$ for $p$ thus takes $O(2^j\log N)$ time. Summing over $j=O(\log f)$, this is $O(f\log N)$ time. Thus, the total time to label each of the $O(f|D_i|)$ faces for all $j=O(\log f)$ is $O(f^2|D_i|\log N)=O(|D_i|{\log }^{3}N)$³³3This time bound here is the dominating factor in the construction time..

Finally, we compute a planar point-location structure for each labeled overlay, which retains the space bound and takes $O(|D_i|f\log N)$ total time. For given $j$ and $\mathrm{\Delta }$ intersected by $q$, the query time to report the largest integer $i^{\prime \prime }\le i+2^j$ that $q$ is contained in each hull $(\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i+1}),\mathrm{\dots },\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i^{\prime \prime }}))$ is $O(\log (2^j{d}^{8+2^j}))=O(j+(8+2^j)\log d)$, as required. $◀$

It remains to show that the computed structures of $D_i$ allow us to compute $\mathrm{𝖲𝖪𝖨𝖯}$ and $\mathrm{𝖥𝖨𝖷}$ sufficiently fast for the outlined telescoping argument above.

Recall the construction of $D_i$ computed for each $\mathrm{\Delta }\in D_i$ and integer $2^{\mathrm{\ell }}=O(f)$ query structures, that allow to answer if $q^{\ast }\in \mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i+1}\cap \mathrm{\dots }\cap S_{i+2^{\mathrm{\ell }}})$, and return the smallest integer $i^{\prime }$ of a $S_{i^{\prime }}$ where it is not contained. Answering a planar point-location query in the overlay for skip-length $2^{\mathrm{\ell }}$ takes $O(2^{\mathrm{\ell }}\log d)$ time. Consequently, answering $j+1$ such queries takes $(2^0+2^1+\mathrm{\dots }+2^j)O(\log d)$ time using the skip-decider structures. $◀$

Recall that Lemma 5 precomputed a point-location structure for the planar subdivision that is the overlay of the subdivisions in $\{\mathrm{𝗁𝗎𝗅𝗅}(\mathrm{\Delta }\cap S_{i^{\prime }}):i^{\prime }\in [i+2^j,i+2^{j+1})\}$. As each region of that subdivision was labeled with the largest integer $i^{\prime \prime }$ where its points are contained in all hull$(\mathrm{\Delta }\cap S_{i^{\prime \prime }})$, we obtain the smallest $i^{\prime }$ in time $O(2^j\log d)=(i^{\prime }-i)O(\log d)$, since $2^j=O(i^{\prime }-i)$. Recall that corner-component membership information was precomputed in construction of $D_i$ for all $i^{\prime }>i$. For any given $i^{\prime }>i$ and connected component of $D_{i^{\prime }}\setminus {\mathrm{𝖲𝖬𝖯𝖫}}_{i^{\prime }}(i^{\prime }-i)$, a point-location query takes $O(\log d^{16+2(i^{\prime }-i)})=(i^{\prime }-i)O(\log d)$ time, and there are $O(1)$ connected components to query. $◀$

Note that both time bounds, of Lemmas 6 and 7, are $(i^{\prime }-i)O(\log d)$, as desired.

Lemmas 2 and 4 showed that the triangle sequence $({\mathrm{\Delta }}_{i_j})$ has a set of planes $\overline{H}=H({\mathrm{\Delta }}_{i_1})\cup \mathrm{\dots }\cup H({\mathrm{\Delta }}_{i_m})$ with $\overline{k}$-lowest$(q,\overline{H})=\overline{k}$-lowest$(q,H)$. The query time of $O(f\log d)=O(\log |H|)$ follows from Lemmas 6 and 7 in the telescoping argument Eq. (1). The amortized update time of $O(fg)=O(f\frac{|H_i|{\log }^{6}N}{d^i})=O({\log }^8|H|)$, follows from Lemma 5, showing a construction time of $O(|D_i|{\log }^3|H|)=O(|H_i|{\log }^6|H|)$, where $|H_i|=O(d^{i+1})$. From Lemma 5, space is dominated by the bound for $D_f$, i.e. $O(f|D_f|)=O(f|H|{\log }^3|H|)$. $◀$

In Subsection 3.1, we introduce a Deduplication Lemma that enables us to apply known techniques for our efficient post-processing PRUNE$(k,\mathrm{\dots })$ of the triangle sequence.