Introduction
High-dimensional data are often represented by vectors, and distances between these vectors measure how different two observations are. Finding a farthest point is a basic operation in diversity maximization, outlier detection, and iterative learning procedures [11 ] . The diameter summarizes the largest separation within the data and is closely related to enclosing balls and clustering [7 , 10 ] . For example, consider a collection of feature vectors that changes as observations arrive or expire. A pair of well-separated current vectors describes the collection’s extent; a farthest-neighbor query asks for an observation most different from a specified vector.
Recomputing either answer by scanning the entire collection can be expensive when such operations are repeated.
For a finite point set P ⊆ R d P \subseteq\mathbb{R}^{d} P ⊆ R d , its Euclidean diameter is diam ( P ) = max x , y ∈ P ∥ x − y ∥ \operatorname{diam}(P) = \max_{x,y\in P} \lVert x-y\rVert diam ( P ) = max x , y ∈ P ∥ x − y ∥ . A factor-c c c diameter pair is a pair x , y ∈ P x,y \in P x , y ∈ P with ∥ x − y ∥ ≥ diam ( P ) / c \lVert x-y\rVert\ge\operatorname{diam}(P)/c ∥ x − y ∥ ≥ diam ( P ) / c . For a query q ∈ R d q \in\mathbb{R}^{d} q ∈ R d , a factor-c c c farthest neighbor is a point p ∈ P p \in P p ∈ P with ∥ q − p ∥ ≥ max x ∈ P ∥ q − x ∥ / c \lVert q-p\rVert\ge\max_{x\in P}\lVert q-x\rVert/c ∥ q − p ∥ ≥ max x ∈ P ∥ q − x ∥ / c ; the query need not belong to P P P . We study fully dynamic diameter, where individual points may be inserted or deleted, and also obtain a farthest-neighbor structure for a fixed point set. The dimension is an input parameter, and our bounds have polynomial dependence on d d d .
Why deletions and adaptivity matter. An insertion can create a new farthest pair, while a deletion can remove an endpoint of the pair currently stored by the algorithm. After such a deletion, the structure must find a sufficiently long pair among the remaining points, even if it has never returned that pair before. Moreover, an application may choose its next update or query after seeing earlier answers. An oblivious adversary fixes the entire operation sequence in advance; an adaptive adversary may use the history of the computation. We allow the latter to see all previous random choices as well as all answers. Only the fresh randomness used after the next operation is fixed remains unknown. This is the robust dynamic model studied in [10 ] . It is also useful when a geometric data structure is called by another algorithm whose later requests depend on its earlier answers.
Previous dynamic and streaming bounds. Indyk’s asymmetric embedding [23 ] 1 gives a fully dynamic factor-c c c diameter approximation with O ~ ( d n 1 / c 2 ) \widetilde{O}(dn^{1/c^{2}}) O ( d n 1/ c 2 ) amortized update time. Its projection lists use O ~ ( d n + n 1 + 1 / c 2 ) \widetilde{O}(dn+n^{1+1/c^{2}}) O ( d n + n 1 + 1/ c 2 ) space. Here n n n bounds the number of active points, and the tilde suppresses logarithmic factors. The guarantee does not provide the exposed-randomness robustness considered here.
A different line achieves an approximation slightly larger than 2 \sqrt{2} 2 with much faster updates. Agarwal and Sharathkumar’s blurred-ball method [7 ] is an insertion-only streaming algorithm: it gives a ( 2 + ε ) (\sqrt{2}+\varepsilon) ( 2 + ε ) -approximate diameter using O ( d ε − 3 log ( 1 / ε ) ) O(d\varepsilon^{-3}\log(1/\varepsilon)) O ( d ε − 3 log ( 1/ ε )) space and amortized update time. Chan and Pathak [15 ] extend the underlying enclosing-ball approach to fully dynamic updates. For fixed ε > 0 \varepsilon> 0 ε > 0 , the resulting diameter structure has O ε ( d log n ) O_{\varepsilon}(d\log n) O ε ( d log n ) expected amortized update time against an oblivious adversary; the diameter consequence is stated explicitly in [10 Appendix A] . Thus insertion-only streaming and fully dynamic maintenance have different guarantees and should be distinguished.
Banihashem et al. [BCG+25] obtain a factor-2 approximation with worst-case poly ( d , log t ) \operatorname{poly}(d,\log t) poly ( d , log t ) update time over t t t updates against an adaptive adversary that sees previous random choices. Their central idea is to use a centerpoint as a representative that remains useful after deletions.2 Their representative is taken in the original space. Our work is motivated by this connection between centerpoints and robust dynamic diameter. We add a squared-norm coordinate before choosing the representative, thereby retaining a variance term that is absent from the original-space argument.
These results leave a clear quantitative question. Above 2 \sqrt{2} 2 , known structures have update time almost linear in the dimension and logarithmic in the set size. Below 2 \sqrt{2} 2 , Indyk’s update bound has a positive power of n n n that approaches 1 / 2 1/2 1/2 as c c c approaches 2 \sqrt{2} 2 . We ask:
Can one maintain a c c c -approximate diameter pair below 2 \sqrt{2} 2 with an update exponent that tends to zero at 2 \sqrt{2} 2 , while supporting arbitrary deletions and fully adaptive updates?
Our answer is affirmative. The same geometry also gives faster farthest-neighbor queries on a fixed data set, with one success event valid for every query vector.
Main results
We first state the dynamic diameter bounds. The capacity n ≥ 2 n \ge2 n ≥ 2 is an upper bound on ∣ P ∣ |P| ∣ P ∣ throughout the execution. For a Monte Carlo structure, t ≥ 1 t \ge1 t ≥ 1 is an upper bound on the number of updates and δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) is the allowed probability that any answer is incorrect. All guarantees below permit the adaptive adversary just defined. A diameter query returns the two stored point identifiers and a reference to their previously computed squared distance in O ( 1 ) O(1) O ( 1 ) time. Writing out coordinates or the exact squared distance takes time proportional to the output length.
The notation poly c ( d , L ) \operatorname{poly}_c(d,L) poly c ( d , L ) denotes a polynomial in d d d and L L L whose degree and coefficients may depend on the fixed approximation factor c c c . In particular, it contains no additional power of n n n . The arithmetic model counts operations and comparisons on coordinates; § 3 also specifies implementations for rational coordinates and the polynomial dependence on their bit length.
The following is our main update bound.
Theorem 1.1 (Fully dynamic diameter below 2 \sqrt{2} 2 ). For every fixed 1 < c < 2 1<c<\sqrt{2} 1 < c < 2 , a fully dynamic structure maintains a factor-c c c diameter pair with worst-case update time n 2 / c 2 − 1 poly c ( d , log ( 2 n t / δ ) ) n^{2/c^2-1}\operatorname{poly}_c(d,\log(2nt/\delta)) n 2/ c 2 − 1 poly c ( d , log ( 2 n t / δ )) and space n 2 / c 2 poly c ( d , log ( 2 n t / δ ) ) n^{2/c^2}\operatorname{poly}_c(d,\log(2nt/\delta)) n 2/ c 2 poly c ( d , log ( 2 n t / δ )) . With probability at least 1 − δ 1-\delta 1 − δ , all answers during the first t t t adaptive updates are correct.
Compared with Indyk’s exponents, both the update and space exponents decrease by $1-1/c^2$ throughout 1 < c < 2 1<c<\sqrt{2} 1 < c < 2 . At c = 3 / 2 c=\sqrt{3}/2 c = 3 /2 , the update exponent decreases from 2 / 3 2/3 2/3 to 1 / 3 1/3 1/3 , and the space exponent from 5 / 3 5/3 5/3 to $4/3. As c c c increases to 2 \sqrt{2} 2 , our update exponent tends to zero and the space exponent tends to one. Figure 1 shows this comparison. The theorem also gives worst-case updates and robustness to exposed previous randomness.
Figure 1. Update exponents as a function of the approximation factor. The red curve improves both exponents of Indyk’s dynamic diameter bound. The green curve uses less space and is the limiting exponent of our always-correct construction; its time has an additional vanishing o ( 1 ) o(1) o ( 1 ) term. The three curves have the distinct space bounds shown in the legend.
The endpoint requires a separate argument: the angular search used below 2 \sqrt{2} 2 is unnecessary there. To state an explicit polynomial bound, put D = d + 3 D=d+3 D = d + 3 and H = ⌈ log 2 ( 2 D n t / δ ) ⌉ H=\lceil\log_2(2Dnt/\delta)\rceil H = ⌈ log 2 ( 2 D n t / δ )⌉ .
Theorem 1.2 (The exact 2 \sqrt{2} 2 endpoint). A fully dynamic structure maintains a factor-2 \sqrt{2} 2 diameter pair with worst-case update time O ( D 19 H 18 ) O(D^{19}H^{18}) O ( D 19 H 18 ) and space O ( n D 19 H 18 ) O(nD^{19}H^{18}) O ( n D 19 H 18 ) . With probability at least 1 − δ 1-\delta 1 − δ , every answer during the first t t t adaptive updates is correct. For rational coordinates of at most B B B bits, an always-correct variant uses n poly ( d , B , log ( 2 n ) ) n\operatorname{poly}(d,B,\log(2n)) n poly ( d , B , log ( 2 n )) space and poly ( d , B , log ( 2 n ) ) \operatorname{poly}(d,B,\log(2n)) poly ( d , B , log ( 2 n )) expected amortized update time, without a prescribed bound on the number of updates.
The displayed polynomial is one explicit bound for the construction; its degrees are not optimized. Lemma 7.2 derives it by substituting the centerpoint construction time and the exact-leaf cutoff into the replacement schedule. The significance of the endpoint is its polylogarithmic dependence on n n n at approximation exactly 2 \sqrt{2} 2 .
Time–space tradeoffs. The main theorem balances the update exponent and the extra exponent above linear space. More generally, let σ \sigma σ specify the space bound n 1 + σ n^{1+\sigma} n 1 + σ , apart from polynomial factors. Write g = c 2 − 1 g=c^2-1 g = c 2 − 1 and ρ = 2 / c 2 − 1 \rho=2/c^2-1 ρ = 2/ c 2 − 1 . For 0 ≤ σ ≤ ρ 0\le\sigma\le\rho 0 ≤ σ ≤ ρ , storing the filter lists explicitly gives update exponent
Q c ( σ ) = ( 1 − g 2 − g σ ) 2 . Q_c(\sigma)=\left(\sqrt{1-g^2}-g\sqrt{\sigma}\right)^2. Q c ( σ ) = ( 1 − g 2 − g σ ) 2 .
Thus Theorem 1.1 extends to the bounds
update time n Q c ( σ ) poly c , σ ( d , log ( 2 n t / δ ) ) , space n 1 + σ poly c , σ ( d , log ( 2 n t / δ ) ) . \begin{aligned}
\text{update time}\quad&n^{Q_c(\sigma)}\operatorname{poly}_{c,\sigma}(d,\log(2nt/\delta)),\\
\text{space}\quad&n^{1+\sigma}\operatorname{poly}_{c,\sigma}(d,\log(2nt/\delta)).
\end{aligned} update time space n Q c ( σ ) poly c , σ ( d , log ( 2 n t / δ )) , n 1 + σ poly c , σ ( d , log ( 2 n t / δ )) .
At σ = ρ \sigma=\rho σ = ρ both exponents beyond the leading linear space factor equal ρ \rho ρ ; at σ = 0 \sigma=0 σ = 0 the update exponent is Q c ( 0 ) = c 2 ( 2 − c 2 ) Q_c(0)=c^2(2-c^2) Q c ( 0 ) = c 2 ( 2 − c 2 ) . These bounds have no n o ( 1 ) n^{o(1)} n o ( 1 ) overhead.
Our second construction improves the update exponent when the space is close to linear. It represents point–filter incidences implicitly and recovers only those needed by a search. The quantities below describe its curve: χ c \chi_c χ c is the exponent at linear space, and u c u_c u c is the point where the improved linear branch meets Q c Q_c Q c . Set
χ c = 2 − 1 + 3 g 2 , u c = g 2 ( 1 − g 2 ) ( 1 + g 2 + 1 + 3 g 2 ) 2 . \chi_c=2-\sqrt{1+3g^2},\qquad u_c=\frac{g^2(1-g^2)}{(1+g^2+\sqrt{1+3g^2})^2}. χ c = 2 − 1 + 3 g 2 , u c = ( 1 + g 2 + 1 + 3 g 2 ) 2 g 2 ( 1 − g 2 ) .
and
Λ c ( σ ) = { χ c − ( 3 − χ c ) σ , 0 ≤ σ ≤ u c , Q c ( σ ) , u c ≤ σ ≤ ρ . \Lambda_c(\sigma)=
\begin{cases}
\chi_c-(3-\chi_c)\sigma, & 0\leq\sigma\leq u_c,\\
Q_c(\sigma), & u_c\leq\sigma\leq\rho.
\end{cases} Λ c ( σ ) = { χ c − ( 3 − χ c ) σ , Q c ( σ ) , 0 ≤ σ ≤ u c , u c ≤ σ ≤ ρ .
The first branch is tangent to Q c Q_c Q c at u c u_c u c , and is strictly below it for 0 ≤ σ < u c 0\leq\sigma<u_c 0 ≤ σ < u c . This improvement comes with a vanishing additive term in the time exponent. It also admits an always-correct (Las Vegas) implementation: randomness affects the work, but never the validity of an answer.
See also Figure 2 for the two curves at a fixed approximation factor.
Figure 2. The time–space tradeoff at c = 9 / 5 c=\sqrt{9/5} c = 9/5 . Space is n 1 + σ n^{1+\sigma} n 1 + σ up to polynomial factors. The implicit construction replaces the initial part of the explicit curve by its tangent at u c ≈ 0.0205 u_c\approx0.0205 u c ≈ 0.0205 , improving the update exponent near linear space. Its running time has an additional vanishing o ( 1 ) o(1) o ( 1 ) term; the space exponent stays 1 + σ 1+\sigma 1 + σ .
Theorem 1.3 (Improved tradeoff with zero error). For fixed $1<c<\sqrt{2}$ and 0 ≤ σ ≤ ρ 0\leq\sigma\leq\rho 0 ≤ σ ≤ ρ , rational points with coordinate bit length at most B B B admit an always-correct fully dynamic factor-c c c diameter structure with space n 1 + σ poly c , σ ( d , B , log ( 2 n ) ) n^{1+\sigma}\operatorname{poly}_{c,\sigma}(d,B,\log(2n)) n 1 + σ poly c , σ ( d , B , log ( 2 n )) and expected amortized update time n Λ c ( σ ) + o ( 1 ) poly c , σ ( d , B , log ( 2 n ) ) n^{\Lambda_c(\sigma)+o(1)}\operatorname{poly}_{c,\sigma}(d,B,\log(2n)) n Λ c ( σ ) + o ( 1 ) poly c , σ ( d , B , log ( 2 n )) . It supports adaptive update sequences of arbitrary length. For a prescribed t t t and δ \delta δ , a Monte Carlo variant has the same exponents, worst-case update time, and polynomial logarithmic dependence on $t/\delta.
Expected amortized time bounds the expected total work over every fixed finite prefix of an adaptive execution starting from the empty set. It includes construction, unsuccessful attempts, and rebuilding. The space bound includes all simultaneously live structures and their workspace. The following quantitative version makes the o ( 1 ) o(1) o ( 1 ) term in Theorem 1.3 explicit.
Corollary 1.4 (Explicit vanishing overhead). The o ( 1 ) o(1) o ( 1 ) in Theorem 1.3 can be replaced by C c , σ ( log ( 2 n ) ) − 1 / 100 C_{c,\sigma}(\log(2n))^{-1/100} C c , σ ( log ( 2 n ) ) − 1/100 for one algorithm and a constant C c , σ C_{c,\sigma} C c , σ depending only on c , σ c,\sigma c , σ . The polynomial degrees in d d d , B B B , log ( 2 n ) \log(2n) log ( 2 n ) are fixed, and the space exponent remains 1 + σ 1+\sigma 1 + σ .
The proof is Theorem D.1 in Appendix § 14 . In particular, increasing the dimension does not change the displayed exponent of n n n . At linear space, that exponent tends to χ c \chi_c χ c ; for c = 1 + ε c=1+\varepsilon c = 1 + ε it equals 1 − 6 ε 2 + O ( ε 3 ) 1-6\varepsilon^2+O(\varepsilon^3) 1 − 6 ε 2 + O ( ε 3 ) . The accuracy is fixed in these statements: the constants need not be polynomial in 1 / ε 1/\varepsilon 1/ ε .
Static diameter and arbitrary farthest-neighbor queries. Inserting all input points immediately gives static diameter algorithms. The geometric reduction also supports arbitrary queries to a fixed data set. These are separate consequences: the fully dynamic theorems maintain one pair, while the static query structure returns a farthest neighbor of any supplied q ∈ R d q\in\mathbb{R}^d q ∈ R d .
Corollary 1.5 (Static Euclidean diameter). For fixed 1 < c < 2 1<c<\sqrt{2} 1 < c < 2 , a factor-c c c diameter pair of n n n points can be found with high probability in n 1 + c 2 ( 2 − c 2 ) poly c ( d , log n ) n^{1+c^2(2-c^2)}\operatorname{poly}_c(d,\log n) n 1 + c 2 ( 2 − c 2 ) poly c ( d , log n ) time and n poly c ( d , log n ) n\operatorname{poly}_c(d,\log n) n poly c ( d , log n ) space. For rational inputs, an always-correct algorithm has expected time n 1 + χ c + o ( 1 ) poly c ( d , B , log n ) n^{1+\chi_c+o(1)}\operatorname{poly}_c(d,B,\log n) n 1 + χ c + o ( 1 ) poly c ( d , B , log n ) and n poly c ( d , B , log n ) n\operatorname{poly}_c(d,B,\log n) n poly c ( d , B , log n ) space.
Proof. Insert the points into the explicit structure with σ = 0 \sigma=0 σ = 0 , or into Theorem 1.3 with σ = 0 \sigma=0 σ = 0 , and return the stored pair.
For a fixed set, Corollary E.1 gives n 1 + o ( 1 ) poly c ( d , log ( n / δ ) ) n^{1+o(1)}\operatorname{poly}_c(d,\log(n/\delta)) n 1 + o ( 1 ) poly c ( d , log ( n / δ )) preprocessing and space, and n c 2 ( 2 − c 2 ) + o ( 1 ) poly c ( d , log ( n / δ ) ) n^{c^2(2-c^2)+o(1)}\operatorname{poly}_c(d,\log(n/\delta)) n c 2 ( 2 − c 2 ) + o ( 1 ) poly c ( d , log ( n / δ )) query time. With probability at least 1 − δ 1-\delta 1 − δ , every real query is answered correctly, including queries chosen after the entire structure and its random choices have been inspected. No upper bound on the number of queries is needed. A zero-error counterpart for rational inputs is stated in Corollary E.2.
At c = 2 − ε c=\sqrt{2}-\varepsilon c = 2 − ε , these results give static diameter time n 1 + O ( ε ) n^{1+O(\varepsilon)} n 1 + O ( ε ) and query time n O ( ε ) + o ( 1 ) n^{O(\varepsilon)+o(1)} n O ( ε ) + o ( 1 ) , with near-linear preprocessing and space for the query structure and polynomial factors in the input parameters. On binary inputs, these Euclidean guarantees also improve the Hamming exponents of Andoni, Jiang, and Zharkov [4 ] . Squared Euclidean distance equals Hamming distance on binary vectors. Taking c = 2 − θ c=\sqrt{2-\theta} c = 2 − θ therefore yields the direct comparison in Table 1 .
Table 1. Static bounds for fixed 0 < θ < 1 0 < \theta< 1 0 < θ < 1 , suppressing polynomial dimension and logarithmic factors. Our diameter algorithms have linear space exponent; our query structures have near-linear preprocessing and space. Zero-error bounds are expected total-work bounds. The exact zero-error diameter exponent is 3 − 4 − 6 θ + 3 θ 2 + o ( 1 ) 3-\sqrt{4-6\theta+3\theta^2}+o(1) 3 − 4 − 6 θ + 3 θ 2 + o ( 1 ) .
Limits on faster updates. We also explain why the dependence on the approximation factor cannot simply be removed. The randomized Orthogonal Vectors Conjecture (OVC) states that, for every constant η > 0 \eta>0 η > 0 , orthogonal pair detection between two n n n -point binary sets in a suitable dimension O ( log n ) O(\log n) O ( log n ) has no bounded-error O ( n 2 − η ) O(n^{2-\eta}) O ( n 2 − η ) -time algorithm [16 ] . Under this hypothesis, a single ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximation scheme cannot have update time n 1 − γ poly ( d , 1 / ε , log n ) n^{1-\gamma}\operatorname{poly}(d,1/\varepsilon,\log n) n 1 − γ poly ( d , 1/ ε , log n ) for a fixed γ > 0 \gamma>0 γ > 0 , a constant-time answer, and fixed polynomial initialization. § 8 proves this by an explicit reduction that pays for initialization only once. This does not conflict with our bounds, whose saving tends to zero as c c c tends to one.
Memory lower bounds concern a different resource. Adapting the insertion-only INDEX reduction of Agarwal–Sharathkumar [7 ] gives a lower bound of Ω c ( n ) \Omega_c(n) Ω c ( n ) bits below 2 \sqrt{2} 2 , already on sign vectors in O c ( log n ) O_c(\log n) O c ( log n ) dimensions (Proposition 8.4). Thus our linear-space exponent is optimal on those bounded-coordinate inputs, up to logarithmic factors. The bound counts the stored data as part of memory; it gives no corresponding lower bound on update time. Our structures explicitly store the active points.
Related work
Geometric reductions and robust representatives. Goel, Indyk, and Varadarajan [17 ] reduce static farthest-neighbor search to nearest-neighbor search using enclosing balls, radial shells, and reflection. Chan and Pathak’s hierarchy [15 ] supplies a dynamic organization, while Banihashem et al. [BCG+25] show how centerpoint depth protects a representative against adaptive deletions. The additional squared-norm coordinate in our construction preserves a variance identity as well as depth. This gives a stronger distance witness than the original-space representative and makes the remaining searches instances of one common angular gap.
Filtering and implicit search. Our angular indices use locality-sensitive filtering [14 , 5 ] . The time–space curve for explicitly stored incidences is consistent with the filtering tradeoffs of [5 ] ; their lower bounds concern the specified search model, rather than arbitrary dynamic diameter structures. Our zero-error construction uses finite norm-splitting families from Wei [31 ] . To reduce space, we combine implicit-set search [1 ] and McCauley’s function-inversion approach [27 ] with complete-preimage recovery [8 ] and dynamic phase techniques [25 ] . We require two additional properties: construction workspace must fit the final space bound, and the cost of recovering a bucket must be charged to its current members after deletions. Recent static preimage-reporting bounds [29 ] do not by themselves supply this dynamic guarantee.
Static and adaptive query algorithms. Polynomial methods and fast matrix multiplication give offline approximate pair algorithms [2 , 3 ] . Andoni–Jiang–Zharkov’s regularity method [4 ] gives Hamming ( 2 − θ ) (2-\theta) ( 2 − θ ) -diameter in n 1 + O ( θ ) + o ( 1 ) d O ( 1 ) n^{1+O(\sqrt{\theta})+o(1)}d^{O(1)} n 1 + O ( θ ) + o ( 1 ) d O ( 1 ) time and the corresponding farthest-neighbor structure; Table 1 records our improvement. Their approximate Orthogonal Vectors algorithm has the different bound n 1 + O ( θ ) + o ( 1 ) n^{1+O(\theta)+o(1)} n 1 + O ( θ ) + o ( 1 ) . Adversarially robust farthest-neighbor search on a fixed data set is studied in [11 ] . Our fixed-set result similarly allows arbitrary adaptive queries, while our dynamic results concern maintenance of the diameter under point insertions and deletions.
Streaming and other update models. Dynamic streaming ε \varepsilon ε -kernels give near-exact extent approximations in fixed dimension [13 ] , with dimension dependence outside the bounds sought here. Small insertion-only diameter summaries are studied in [19 ] . The expiration-streaming model [9 ] supplies deletion times when points arrive; our model does not. The merge-only partition structure of Bathie–Lagarde [12 ] has another update model. Polynomial streaming-space lower bounds for general metrics [26 ] and Euclidean strict-turnstile streams [28 ] further describe the memory needed when the input is not retained. The latter allows arbitrary stream length and multiplicities. Polynomial-length sketch simulations [24 ] have separate assumptions, which we keep distinct in § 8 .
Our approach and techniques
The proof has three main ingredients. First, we strengthen the centerpoint method for adaptive dynamic diameter of Banihashem et al. [10 ] : a center chosen after adding one coordinate also records the spread of the points. This gives an exact 2 \sqrt{2} 2 -approximation that survives deletions. Second, any pair that this approximation misses at a factor c < 2 c < \sqrt{2} c < 2 satisfies a useful angular separation. We search for such pairs by filtering, and maintain a small set of candidate pairs by a matching. Third, we improve the space bound by recovering filter lists when they are needed, instead of storing every list explicitly. The first two ingredients yield the balanced bound; the third yields the improved tradeoff near linear space. We explain the geometry first and then the dynamic implementation.
A center that records the spread of the points
For a center o o o in the convex hull of a point set, every query q q q has some point at distance at least ∥ q − o ∥ \lVert q-o\rVert ∥ q − o ∥ . This is the lower bound used by the original-space centerpoint approach [10 ] ; combined with the triangle inequality, it gives factor two. To improve that argument, we retain a second quantity. Suppose nonnegative weights λ p \lambda_p λ p sum to one and satisfy ∑ p λ p p = o \sum_p \lambda_p p = o ∑ p λ p p = o . Their variance about o o o is V = ∑ p λ p ∥ p − o ∥ 2 V=\sum_p \lambda_p\lVert p-o\rVert^2 V = ∑ p λ p ∥ p − o ∥ 2 . Then
∑ p λ p ∥ p − q ∥ 2 = ∥ q − o ∥ 2 + V . \sum_p \lambda_p\lVert p-q\rVert^2 = \lVert q-o\rVert^2 + V. p ∑ λ p ∥ p − q ∥ 2 = ∥ q − o ∥ 2 + V .
Consequently some point is at distance at least ∥ q − o ∥ 2 + V \sqrt{\lVert q - o\rVert^2 + V} ∥ q − o ∥ 2 + V from q q q . The extra term V V V is the improvement we need. The difficulty is to preserve it when the adversary deletes points: one deletion can invalidate a particular convex combination.
We obtain many witnesses to the same inequality by taking a centerpoint in one higher dimension. At the construction of a local structure, let P 0 P_0 P 0 be its fixed set of m m m points, called its birth set . Replace each p p p by its paraboloid lift p + = ( p , ∥ p ∥ 2 ) p^+ = (p, \lVert p\rVert^2) p + = ( p , ∥ p ∥ 2 ) . Choose a point z = ( o , s ) ∈ R d + 1 z = (o, s) \in\mathbb{R}^{d+1} z = ( o , s ) ∈ R d + 1 of halfspace depth at least α m \alpha m α m , where s s s is a real number and α − 1 \alpha^{-1} α − 1 is polynomial in the dimension and the logarithmic accuracy parameters.3 Write V = s − ∥ o ∥ 2 V = s - \lVert o\rVert^2 V = s − ∥ o ∥ 2 . Since positive depth puts z z z in the convex hull of the lifted points, V V V is the variance of every convex combination representing z z z , and in particular V ≥ 0 V \ge0 V ≥ 0 .
The benefit of the lift is that squared-distance inequalities become linear inequalities in ( p , ∥ p ∥ 2 ) (p, \lVert p\rVert^2) ( p , ∥ p ∥ 2 ) . Two halfspaces whose boundaries pass through z z z therefore give
∣ { p ∈ P 0 : ∥ p − o ∥ 2 ≤ V } ∣ ≥ α m , \lvert\{p \in P_0 : \lVert p - o\rVert^2 \le V\}\rvert\ge\alpha m, ∣{ p ∈ P 0 : ∥ p − o ∥ 2 ≤ V }∣ ≥ α m ,
∣ { p ∈ P 0 : ∥ p − q ∥ 2 ≥ ∥ q − o ∥ 2 + V } ∣ ≥ α m for every q ∈ R d . \lvert\{p \in P_0 : \lVert p - q\rVert^2 \ge\lVert q - o\rVert^2 + V\}\rvert\ge\alpha m \qquad\text{for every } q \in\mathbb{R}^d. ∣{ p ∈ P 0 : ∥ p − q ∥ 2 ≥ ∥ q − o ∥ 2 + V }∣ ≥ α m for every q ∈ R d .
The first set is the part of the data inside the core ball B ( o , V ) B(o, \sqrt{V}) B ( o , V ) . The second consists of points that witness the improved distance lower bound for q q q . The witnesses need not belong to the core. After a birth points are deleted, both counts decrease by at most a a a , simultaneously for every q q q . This deterministic statement is what allows the query and the deletions to depend on earlier answers and random choices.
A chain of cores. A node is one local structure with a fixed center o o o , variance V V V , and a changing input set S S S . Its current core is C = S ∩ B ( o , V ) C = S \cap B(o, \sqrt{V}) C = S ∩ B ( o , V ) ; its child receives the residual S ∖ C S \setminus C S ∖ C . Repeating this construction gives a chain, ending when the residual is small enough to inspect all pairs. Each node is replaced after at most α m / 16 \alpha m/16 α m /16 changes to its input. During this lifetime, its core contains a constant fraction of α m \alpha m α m surviving birth points. Hence each successive input loses an Ω ( α ) \Omega(\alpha) Ω ( α ) fraction, and the chain has O ( α − 1 log n ) O(\alpha^{-1}\log n) O ( α − 1 log n ) nodes.
At a node, a balanced search tree maintains the point y ∈ S y \in S y ∈ S maximizing the radius R = ∥ y − o ∥ R = \lVert y-o\rVert R = ∥ y − o ∥ . Apply the witness inequality with q = y q=y q = y , and store an actual pair { y , p } \{y,p\} { y , p } of length L ≥ R 2 + V L \ge\sqrt{R^2+V} L ≥ R 2 + V . Fresh uniform samples from S S S find such a point p p p with high probability: many birth witnesses still survive, even when the adversary chose y y y after seeing all earlier randomness. The update uses new random choices after y y y has been fixed.
To see why these local pairs suffice, consider a pair x , y x,y x , y attaining the global diameter. Follow the chain until the first core containing either endpoint, say x x x . Both endpoints are still in that node’s input, so ∥ x − o ∥ ≤ V \lVert x-o\rVert\le\sqrt{V} ∥ x − o ∥ ≤ V and ∥ y − o ∥ ≤ R \lVert y-o\rVert\le R ∥ y − o ∥ ≤ R . Therefore
∥ x − y ∥ ≤ V + R ≤ 2 V 2 + R 2 ≤ 2 L . \lVert x-y\rVert\le\sqrt{V}+R \le\sqrt{2\sqrt{V^2+R^2}} \le\sqrt{2}L. ∥ x − y ∥ ≤ V + R ≤ 2 V 2 + R 2 ≤ 2 L .
If both endpoints reach the terminal set, its exact diameter suffices. Thus the longest stored local pair and the exact terminal answer give factor 2 \sqrt{2} 2 . The approximation is applied only at the first core containing an endpoint; it is not multiplied along the chain.
Making the witnesses always correct. For the zero-error structure, the center comes with many disjoint small blocks of birth points. For each block we store nonnegative coefficients that sum to one and express z z z as the weighted average of its lifted points. These equalities can be checked exactly. An intact block is one from which no point has been deleted; its coefficients prove the variance identity for every query. Scanning one intact block therefore finds a valid witness without a probability of error. A deletion invalidates at most one block because the blocks are disjoint. We accept a randomly constructed center only after checking the block certificates and the core size, retrying otherwise. This changes randomness from a possible source of incorrect answers into a source of variation in construction time.
Improving the approximation by searching directions
The 2 \sqrt{2} 2 construction already answers many of the searches needed for a better factor. Suppose a core point p p p is at distance at least τ \tau τ from a query q q q , but the stored baseline gives no distance as large as τ / c \tau/c τ / c . Put r = ∥ p − o ∥ r=\lVert p-o\rVert r = ∥ p − o ∥ and Q = ∥ q − o ∥ Q=\lVert q-o\rVert Q = ∥ q − o ∥ , and group points with similar radii into shells. For the moment, consider an exact shell of radius r > 0 r>0 r > 0 and assume Q > 0 Q>0 Q > 0 ; zero radii are handled by the baseline. Let u = ( p − o ) / r u=(p-o)/r u = ( p − o ) / r and z = − ( q − o ) / Q z=-(q-o)/Q z = − ( q − o ) / Q . Negating the query direction turns a large distance into a large inner product:
∥ p − q ∥ 2 = r 2 + Q 2 + 2 r Q ⟨ u , z ⟩ . \lVert p-q\rVert^2=r^2+Q^2+2rQ\langle u,z\rangle. ∥ p − q ∥ 2 = r 2 + Q 2 + 2 r Q ⟨ u , z ⟩ .
A point at distance at least τ \tau τ has correlation at least a a a , whereas a point at distance at most τ / c \tau/c τ / c has correlation at most b b b , for
a = τ 2 − r 2 − Q 2 2 r Q , b = τ 2 / c 2 − r 2 − Q 2 2 r Q . a=\frac{\tau^2-r^2-Q^2}{2rQ},\qquad b=\frac{\tau^2/c^2-r^2-Q^2}{2rQ}. a = 2 r Q τ 2 − r 2 − Q 2 , b = 2 r Q τ 2 / c 2 − r 2 − Q 2 .
Here the core condition gives r 2 ≤ V r^2\le V r 2 ≤ V , and failure of the baseline gives τ 2 / c 2 > V + Q 2 \tau^2/c^2>V+Q^2 τ 2 / c 2 > V + Q 2 . Thus b > 0 b>0 b > 0 . The same facts imply a ≥ c 2 b + ( c 2 − 1 ) a\ge c^2b+(c^2-1) a ≥ c 2 b + ( c 2 − 1 ) . This is the crucial separation: it is stronger than an arbitrary pair of angular thresholds.
Append one coordinate with opposite signs to the two unit vectors. This changes their correlation w w w to ( w − b ) / ( 1 + b ) (w-b)/(1+b) ( w − b ) / ( 1 + b ) . The points we must find now have correlation at least g = c 2 − 1 g=c^2-1 g = c 2 − 1 , while all unacceptable answers have correlation at most zero. Every shell pair therefore reduces to the same search problem, independent of r r r and Q Q Q . § 5 implements this idealized calculation with inward radial rounding, rational coordinates, and small margins at the thresholds.
For a concrete illustration, take r = Q = V = 1 r=Q=\sqrt{V}=1 r = Q = V = 1 , c = 3 / 2 c=\sqrt{3/2} c = 3/2 , and τ = 2 \tau=2 τ = 2 . Then a = 1 a=1 a = 1 , b = 1 / 3 b=1/3 b = 1/3 , and the baseline guarantee 2 \sqrt{2} 2 is smaller than the required distance τ / c = 8 / 3 \tau/c=\sqrt{8/3} τ / c = 8/3 . Padding maps the target correlation to ( 1 − 1 / 3 ) / ( 1 + 1 / 3 ) = 1 / 2 = c 2 − 1 (1-1/3)/(1+1/3)=1/2=c^2-1 ( 1 − 1/3 ) / ( 1 + 1/3 ) = 1/2 = c 2 − 1 , while every unacceptable correlation becomes nonpositive. Thus the padded target lies at angle 60 ∘ 60^\circ 6 0 ∘ from the padded query, whereas every unacceptable point lies at angle at least 90 ∘ 90^\circ 9 0 ∘ .
A filter is a subset of directions selected by a random Gaussian projection. A point and a query with sufficiently large correlation are likely to belong to a common filter. We use different projection thresholds for stored points and queries, trading the number of copies of each point against query work. With threshold ratio x x x , the data replication and query exponents are
u = ( x − g ) 2 1 − g 2 , v = ( 1 − g x ) 2 1 − g 2 . u=\frac{(x-g)^2}{1-g^2},\qquad v=\frac{(1-gx)^2}{1-g^2}. u = 1 − g 2 ( x − g ) 2 , v = 1 − g 2 ( 1 − g x ) 2 .
Thus a birth set of size m m m uses about m 1 + u m^{1+u} m 1 + u space and m v m^v m v work per search, apart from polynomial and logarithmic factors. Choosing x = g + σ 1 − g 2 x=g+\sigma\sqrt{1-g^2} x = g + σ 1 − g 2 sets u = σ u=\sigma u = σ and v = Q c ( σ ) v=Q_c(\sigma) v = Q c ( σ ) . The symmetric choice x = 1 x=1 x = 1 gives u = v = ( 1 − g ) / ( 1 + g ) = 2 / c 2 − 1 u=v=(1-g)/(1+g)=2/c^2-1 u = v = ( 1 − g ) / ( 1 + g ) = 2/ c 2 − 1 , explaining the balanced exponent. The formal proof chooses margins of order 1 / log n 1/\log n 1/ log n ; their effect on an exponent is O c ( 1 / log n ) O_c(1/\log n) O c ( 1/ log n ) and therefore changes the running time by only a constant factor. This is why the explicit construction has the stated powers of n n n without an additional n o ( 1 ) n^{o(1)} n o ( 1 ) factor.
Maintaining a pair, rather than answering one search
A farthest-neighbor search starts with a specified query point. Maintaining the diameter is different: after the reported pair loses an endpoint, neither endpoint of its replacement is known. At each node and distance scale, we use a bipartite graph whose left vertices are core points and whose right vertices are eligible input points. A strong edge is a pair that must be detected; a weak edge is a pair whose distance is already good enough to report at that scale. Every strong edge is weak. The angular search finds an actual weak neighbor whenever a strong neighbor exists.
Maintain a matching of weak edges, with unmatched sets U L U_L U L and U R U_R U R , subject to the invariant
No strong edge has one endpoint in U L U_L U L and one in U R U_R U R .
Algorithm 1 The local matching rule (overview)
When a vertex v v v becomes unmatched, search the opposite unmatched set.
if a weak neighbor w w w is found then
Match v v v with w w w and remove w w w from its unmatched set.
else
Keep v v v in its unmatched set.
end if
On deletion, remove the incident matching edge, if any, and apply the rule to its surviving endpoint.
Report any matching edge, if one exists.
This does not require a maximum matching. It requires only one search when a vertex first becomes unmatched. If a strong edge exists, the matching cannot be empty, so any matching edge supplies a candidate pair.
A point has at most one copy on each side. Deleting it frees at most two surviving partners, so one point update causes only constantly many searches per configuration. The detailed algorithm removes both copies before repairing either side, and verifies every candidate’s original distance.
The distance scales are measured relative to V \sqrt{V} V , not to the largest input coordinate. If the maximum radius R R R is much larger than V \sqrt{V} V , the baseline already gives factor c c c . Otherwise, all relevant radii lie in a bounded interval around V \sqrt{V} V and can be rounded inward. A rounded pair is justified either by its original distance or by the current baseline. Consequently deleting a faraway point does not force every shell to be rescaled, and the bounds do not depend on the spread of the coordinates.
Why exposed randomness does not invalidate the searches. An adversary that sees a filter family’s random choices could choose a newly inserted point specifically for that family. We avoid this dependence by choosing each family’s randomness only after fixing its birth set. An old family subsequently handles deletions from that set. We divide the chronological sequence of insertion occurrences into intervals of lengths 1 , 2 , 4 , … 1, 2, 4, \ldots 1 , 2 , 4 , … and build a family for a completed interval. Reinserting a deleted point creates a new occurrence. Smaller completed intervals continue to answer searches while a larger family is being built. The success event for each family holds for every query direction and every subset of its birth set, so revealing its random choices does not weaken that event.
The center chain also needs replacements. Building a new chain from top to bottom without a schedule could leave a small residual’s center too old by the time the entire chain is ready. Instead, all nodes in a replacement chain share an activation deadline. A residual of size m m m is opened only when O ( α m ) O(\alpha m) O ( α m ) updates remain before that deadline, and its construction finishes in O ( α 2 m ) O(\alpha^{2}m) O ( α 2 m ) updates. The input shrinks by an Ω ( α ) \Omega(\alpha) Ω ( α ) fraction at each level, so these opening times leave room for the next node. Each activated node retains its actual age. A chain under construction does not start further replacement chains. § 7 proves that these rules finish the work on time with only polynomial and logarithmic overhead.
Using less space by recovering filter lists
Explicit filters store a separate record whenever a point belongs to a filter. The improved tradeoff keeps the same geometric search idea, but represents these point–filter incidences implicitly. Two issues must be resolved: a family must cover all valid queries, and its lists must remain efficient to recover after arbitrary deletions.
Coverage that can be checked. We divide the coordinates into mutually orthogonal blocks. A pair with large correlation has large normalized correlation in at least one block. Within a block, the finite splitting families of Wei [31 ] reduce coverage to spheres of much smaller dimension. On each small sphere, a finite, sufficiently fine set of directions allows us to check that a sampled family covers every relevant pair. A positive margin extends the checked property from the finite set to the whole sphere. We retry until the check succeeds. Every accepted family is therefore correct. Random rotations are used to bound the number of irrelevant candidates examined during a search; a bad rotation can increase work, but it cannot remove the guarantee that a good candidate is covered.
The resulting family is a product of small families. Its labels can be counted and selected without writing out the product: two lists of lengths two and three, for instance, define six pairs, and a rank identifies one pair by quotient and remainder. Applying the same mixed-radix calculation to all blocks gives a subpolynomial-time oracle for the j j j th label of a point. We assign each point to an accepted family in which it has at most R R R labels. All its labels in that family are retained; none is discarded to obtain the bound.
One function represents every incidence. For a birth set of m m m points, define a virtual function on { 1 , … , m } × { 1 , … , R } \{1,\ldots,m\} \times\{1,\ldots,R\} { 1 , … , m } × { 1 , … , R } : at ( p , j ) (p,j) ( p , j ) it returns the j j j th filter label of p p p , or a null value if that occurrence is absent. The function is evaluated by the rank oracle, not stored as an array. For a query label, recovering its complete inverse image reveals the corresponding point occurrences. Making the rank part of the function’s domain lets one inverse query recover the entire list.
Let M = m R M=mR M = m R and let τ \tau τ be the inversion parameter. The inverse data structure uses roughly M / τ M/\tau M / τ space and recovers a bounded list in roughly τ 3 \tau^3 τ 3 function evaluations. Both its final representation and the workspace used to construct it must fit the space bound. A deletion changes every occurrence of that point to null, which creates the next difficulty: a list that was large at construction may later have very few surviving members.
We split lists into buckets with certified birth sizes between τ / 16 \tau/16 τ /16 and τ \tau τ . A bucket remains implicit while at least τ / 32 \tau/32 τ /32 members survive. If a query rejects all of these members, its recovery cost can be charged to O ~ ( τ 2 ) \widetilde{O}(\tau^2) O ( τ 2 ) per current rejected occurrence. When a bucket becomes smaller, we recover and explicitly store its remaining members. At least τ / 32 \tau/32 τ /32 deletions have then occurred in that bucket, paying for the small explicit remainder. Rebuilding after O ( M / τ ) O(M/\tau) O ( M / τ ) deletions keeps all such remainders within the space bound. If a search generates Q Q Q labels and encounters F F F rejected current occurrences, its cost is
O ~ ( ( Q + 1 ) τ 3 + F τ 2 ) . \widetilde{O}\bigl((Q+1)\tau^3+F\tau^2\bigr). O ( ( Q + 1 ) τ 3 + F τ 2 ) .
Occurrences are counted with multiplicity: a point lying in several queried filters contributes once for each such incidence. The displayed bound is deterministic and remains valid after adaptive deletions.
Reducing filter density decreases the space for incidences but changes both the number of query labels and the number of rejected candidates. Balancing these two terms with the M / τ M/\tau M / τ space bound gives the linear branch of Λ c ( σ ) \Lambda_c(\sigma) Λ c ( σ ) , tangent to the explicit-filter curve. At linear space its exponent is χ c = 2 − 1 + 3 ( c 2 − 1 ) 2 \chi_c=2-\sqrt{1+3(c^2-1)^2} χ c = 2 − 1 + 3 ( c 2 − 1 ) 2 . § 9 performs the optimization and verifies that construction, updates, and rebuilding fit the same bound.
Finally, correct certificates alone do not bound running time against an adversary that sees every random choice. We race independent certified copies for a prescribed amount of work and fall back to an exact scan if all copies are slow. Amplifying over a finite set of representative directions makes this fallback rare simultaneously for all queries. A bad construction can still be selected by the adversary, so the proof charges all work it can cause during its lifetime to its construction. This gives the expected total-work bound for every fixed finite prefix of an arbitrarily long adaptive sequence. For the worst-case Monte Carlo version, constructors and searches are stopped at fixed budgets; the probability of exhausting a budget is included in the global failure probability.
Model and notation
This section specifies the updates, the information available to the adversary, and the computational costs used in our statements. The geometric terminology needed for the proofs follows in § 4 .
Points and updates. The active data form a finite indexed set P P P of points in R d \mathbb{R}^{d} R d , with ∣ P ∣ ≤ n \lvert P\rvert\le n ∣ P ∣ ≤ n at all times. An insertion supplies a new identity and its d d d coordinates; a deletion specifies a currently active identity. Coordinates remain fixed until that identity is deleted. Different identities may have identical coordinates, and reinsertion starts a new insertion lifetime. No future deletion time is supplied. Internally, the algorithm uses reusable handles returned on insertion. Reading an external name supplied by the user is charged to that name’s length.
The diameter is diam ( P ) = max x , y ∈ P ∥ x − y ∥ \operatorname{diam}(P) = \max_{x,y \in P} \lVert x-y\rVert diam ( P ) = max x , y ∈ P ∥ x − y ∥ , with value zero when ∣ P ∣ ≤ 1 \lvert P\rvert\le1 ∣ P ∣ ≤ 1 . For ∣ P ∣ ≥ 2 \lvert P\rvert\ge2 ∣ P ∣ ≥ 2 , the structure returns two distinct active identities, including when all coordinates coincide. A factor-c c c answer has distance between diam ( P ) / c \operatorname{diam}(P)/c diam ( P ) / c and diam ( P ) \operatorname{diam}(P) diam ( P ) . The algorithm stores the answer’s identities and exact squared distance during updates. Retrieving the identities and a reference to this stored value takes constant time; writing coordinates or the squared distance takes time proportional to the output length.
Adaptive adversaries and probability of error. Before an external operation begins, the adversary specifies that operation using the complete preceding history, including every previous random choice and answer. The algorithm then uses fresh randomness to process it. Internal searches and matching repairs may also depend on earlier random choices. An oblivious adversary is the special case in which the operation sequence is fixed in advance.
A Monte Carlo statement is supplied with a capacity n n n , an upper bound t t t on the number of updates, and a total error probability δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) . With probability at least 1 − δ 1-\delta 1 − δ , every answer in that execution satisfies its approximation guarantee. An always-correct, or Las Vegas, structure is supplied with no update horizon: all its answers are valid, and each operation terminates with probability one. Its expected amortized bound means a bound on the expected total work during every fixed finite prefix of an adaptive execution, divided by that prefix’s length. It does not assert a conditional expected-time bound for each operation after particular random choices have been exposed. Unless stated otherwise, executions start empty; constructing an initial set by insertion is charged to those insertions.
Arithmetic and finite representations. In the arithmetic-RAM model, exact arithmetic operations and comparisons on coordinates have unit cost. For rational inputs, B B B bounds the binary encoding length of each coordinate, including its numerator and denominator. The finite-word implementations account for the lengths of intermediate numbers and have polynomial dependence on B B B . Linear-programming costs are included; no strongly polynomial linear-programming algorithm is assumed. Linear programs use the original lifted coordinates. Normalized vectors and square roots may be used to describe the geometry, while the implementation uses signs and squared rational comparisons whenever possible.
The approximation and space parameters are fixed independently of n n n , d d d , B B B . They are either rational, or can be approximated in polynomial time by rational intervals of length 2 − k 2^{-k} 2 − k that are guaranteed to contain the parameter. This is the meaning of a certified k k k -bit approximation. We round these parameters in the direction required by the inequalities in the proof.
Suppressed factors. We use P \mathcal{P} P for a polynomial in d d d , the coordinate bit length when relevant, and the logarithmic parameters of the statement. Its coefficients and degree may depend on the fixed approximation and space parameters, but not on the input. The polynomial may be enlarged between inequalities. Any dependence on an additional exponent allowance is stated explicitly. The notation O ~ \widetilde{O} O suppresses logarithmic factors only; powers such as n η n^\eta n η and n o ( 1 ) n^{o(1)} n o ( 1 ) are shown explicitly, including in construction workspace. Space counts the active input as well as all auxiliary structures, simultaneous rebuilds, and temporary memory.
Geometric preliminaries
The basic certificate has two purposes: to place many points in a bounded region and to supply many actual points witnessing a distance lower bound. We define its objects here so that the statements in the next section can be concise. Figure 3 and Figure 4 illustrate the geometry and the way these certificates are organized.
Figure 3. Two examples of the certificate. In (a), the nine points 0 , ± e 1 , ± e 2 , ± 2 e 1 , ± 2 e 2 0, \pm e_1, \pm e_2, \pm2e_1, \pm2e_2 0 , ± e 1 , ± e 2 , ± 2 e 1 , ± 2 e 2 admit o = 0 o = 0 o = 0 , V = 1 V = 1 V = 1 ; the core and residual are shown in the original plane. In (b), the one-dimensional points − 2 , − 1 , 0 , 1 , 2 -2, -1, 0, 1, 2 − 2 , − 1 , 0 , 1 , 2 lift to ( p , p 2 ) (p, p^2) ( p , p 2 ) . The point z = ( 0 , 1 ) z = (0, 1) z = ( 0 , 1 ) lies in the convex hulls of two disjoint blocks, { − 1 , 1 } \{-1, 1\} { − 1 , 1 } and { − 2 , 0 , 2 } \{-2, 0, 2\} { − 2 , 0 , 2 } , so its depth is at least two. The halfspace h ≤ 1 h \le1 h ≤ 1 selects the core. For q = 3 / 2 q = 3/2 q = 3/2 , the halfspace h ≥ 3 p + 1 h \ge3p + 1 h ≥ 3 p + 1 selects exactly the two leftmost distance witnesses.
Figure 4. The cores partition the active set together with the terminal set. A diametral pair is analyzed at the first core containing one of its endpoints. The other endpoint is still available in that node’s input.
Halfspace depth and centerpoints. Let Q Q Q be a finite indexed point set in R k \mathbb{R}^k R k . The halfspace depth , also called Tukey depth , of z z z in Q Q Q is
depth Q ( z ) = min { ∣ Q ∩ H ∣ : H is a closed halfspace containing z } . \operatorname{depth}_{Q}(z) = \min\{|Q \cap H| : H \text{ is a closed halfspace containing } z\}. depth Q ( z ) = min { ∣ Q ∩ H ∣ : H is a closed halfspace containing z } .
Point identities are counted with multiplicity if coordinates coincide. A point of depth at least α ∣ Q ∣ \alpha|Q| α ∣ Q ∣ is an α \alpha α -centerpoint . This definition asks for a depth guarantee, not for maximum possible depth. We use approximate centerpoint constructions whose running time is polynomial in the dimension; the precise guarantees and finite representations are given in Appendix § 11 .
For a concrete planar example, the five lifted points in Figure 3 (b) have two disjoint subsets whose convex hulls contain z z z . Every closed halfspace containing z z z must meet each subset, so the depth is at least two. More generally, such representations provide a certificate of depth. Positive depth also implies that z z z lies in the convex hull of Q Q Q : otherwise a separating halfspace containing z z z would contain no point of Q Q Q .
Birth sets, lifting, and variance. When a local structure is constructed, its initial fixed set P 0 P_0 P 0 is called its birth set or birth pool ; write m = ∣ P 0 ∣ m = |P_0| m = ∣ P 0 ∣ . The word “birth” distinguishes this fixed set from the points that remain after later updates. The paraboloid lift maps a point p ∈ R d p \in\mathbb{R}^d p ∈ R d to p + = ( p , ∥ p ∥ 2 ) ∈ R d + 1 p^+ = (p,\|p\|^2) \in\mathbb{R}^{d+1} p + = ( p , ∥ p ∥ 2 ) ∈ R d + 1 ; let P 0 + = { p + : p ∈ P 0 } P_0^+ = \{p^+ : p \in P_0\} P 0 + = { p + : p ∈ P 0 } . Write a positive-depth point of this lifted set as z = ( o , s ) z = (o,s) z = ( o , s ) , with o ∈ R d o \in\mathbb{R}^d o ∈ R d and s ∈ R s \in\mathbb{R} s ∈ R , and set V = s − ∥ o ∥ 2 V = s - \|o\|^2 V = s − ∥ o ∥ 2 . If λ p ≥ 0 \lambda_p \ge0 λ p ≥ 0 sum to one and z = ∑ p λ p p + z = \sum_p \lambda_p p^+ z = ∑ p λ p p + , then
∑ p λ p p = o , V = ∑ p λ p ∥ p − o ∥ 2 ≥ 0. \sum_p \lambda_p p = o,\qquad V = \sum_p \lambda_p\|p-o\|^2 \ge0. p ∑ λ p p = o , V = p ∑ λ p ∥ p − o ∥ 2 ≥ 0.
Thus V V V is the variance associated with the representation. It need not be the variance of the uniform distribution on P 0 P_0 P 0 .
Core and witness halfspaces. The core ball is B ( o , V ) B(o,\sqrt{V}) B ( o , V ) . A variance witness for a query q q q is a point p p p satisfying ∥ p − q ∥ 2 ≥ V + ∥ q − o ∥ 2 \lVert p-q\rVert^2 \ge V+\lVert q-o\rVert^2 ∥ p − q ∥ 2 ≥ V + ∥ q − o ∥ 2 . These two geometric conditions are linear in the lifted coordinates. For a general lifted-space point ( x , h ) ∈ R d + 1 (x,h)\in\mathbb{R}^{d+1} ( x , h ) ∈ R d + 1 , define
H c o r e = { ( x , h ) : h − 2 ⟨ o , x ⟩ ≤ s − 2 ∥ o ∥ 2 } , H_{\mathrm{core}}=\{(x,h):h-2\langle o,x\rangle\le s-2\lVert o\rVert^2\}, H core = {( x , h ) : h − 2 ⟨ o , x ⟩ ≤ s − 2 ∥ o ∥ 2 } ,
H q = { ( x , h ) : h − 2 ⟨ q , x ⟩ ≥ s − 2 ⟨ q , o ⟩ } . H_q=\{(x,h):h-2\langle q,x\rangle\ge s-2\langle q,o\rangle\}. H q = {( x , h ) : h − 2 ⟨ q , x ⟩ ≥ s − 2 ⟨ q , o ⟩} .
Both boundaries pass through z z z . Expanding squared distances shows that p + ∈ H c o r e p^+\in H_{\mathrm{core}} p + ∈ H core exactly when p ∈ B ( o , V ) p\in B(o,\sqrt{V}) p ∈ B ( o , V ) , and p + ∈ H q p^+\in H_q p + ∈ H q exactly when p p p is a variance witness for q q q . The next section applies halfspace depth to these two sets, then counts how many witnesses remain after deletions.
Nodes, cores, and residuals. A node stores one center o o o , one variance V V V , and auxiliary structures for a changing input set S S S . Its current core is C = S ∩ B ( o , V ) C=S\cap B(o,\sqrt{V}) C = S ∩ B ( o , V ) , and its residual is S ∖ C S\setminus C S ∖ C . The residual becomes the input to the next node in a chain; a small terminal set is handled exactly. The birth set determines the node’s center, while its current input determines which points and candidate pairs are still present. Its age is the number of changes to its input since the snapshot used to construct it. Rebuilding replaces the node before too many of its birth witnesses can disappear.
A block certificate for z z z is a subset of birth identities with explicitly stored nonnegative convex coefficients expressing z z z in that block’s lifted convex hull. It is intact when none of those identities has been deleted. Disjoint block certificates are useful because deleting one identity invalidates at most one block. Their role in obtaining always-correct distance witnesses is proved in the next section.
Variance certificates and local witness matchings
This section proves the geometric guarantee independently of the search implementation. At each node of a chain, we remove a large core from the node’s input and maintain a pair that approximates every distance from that core to the input. Every pair of points is assigned to the first core containing one of its endpoints, so these local guarantees imply the global diameter guarantee without multiplying approximation factors along the chain.
We proceed in four steps. First, the lifted centerpoint supplies a distance witness that remains available after deletions; this alone gives factor 2 \sqrt{2} 2 . Second, for smaller c c c we restrict attention to a bounded radial range and round the radii. Third, a matching maintains one witness at each relevant distance scale. Finally, we reduce every resulting search to the same angular problem. The definitions of birth pools, cores, and witnesses are given in § 4 ; Figure 3 and Figure 4 illustrate their roles.
A centerpoint that also certifies variance
Fix a node’s birth pool P 0 P_0 P 0 of m m m point identities. Its coordinates are fixed before the node is constructed. Lift each point to p + = ( p , ∥ p ∥ 2 ) ∈ R d + 1 p^+=(p,\lVert p\rVert^2)\in\mathbb{R}^{d+1} p + = ( p , ∥ p ∥ 2 ) ∈ R d + 1 , and let z = ( o , s ) z=(o,s) z = ( o , s ) have halfspace depth at least α m \alpha m α m in P 0 + P_0^+ P 0 + . Here o ∈ R d o\in\mathbb{R}^d o ∈ R d and s ∈ R s\in\mathbb{R} s ∈ R . Since positive depth places z z z in the convex hull of the lifted points, some convex coefficients λ p \lambda_p λ p satisfy o = ∑ p λ p p o=\sum_p\lambda_p p o = ∑ p λ p p and s = ∑ p λ p ∥ p ∥ 2 s=\sum_p\lambda_p\lVert p\rVert^2 s = ∑ p λ p ∥ p ∥ 2 . Consequently V = s − ∥ o ∥ 2 = ∑ p λ p ∥ p − o ∥ 2 ≥ 0 V=s-\lVert o\rVert^2=\sum_p\lambda_p\lVert p-o\rVert^2\ge0 V = s − ∥ o ∥ 2 = ∑ p λ p ∥ p − o ∥ 2 ≥ 0 . This explains the term variance certificate : the point z z z records both a mean and the second moment of a distribution on the birth points.
The usefulness of depth is that we need not preserve this particular convex combination. The next lemma gives many witnesses for every query at once, so deleting a few points cannot destroy the guarantee.
Lemma 5.1 (Core points and distance witnesses). At least α m \alpha m α m birth points lie in B ( o , V ) B(o,\sqrt{V}) B ( o , V ) . For every q ∈ R d q\in\mathbb{R}^d q ∈ R d , at least α m \alpha m α m birth points satisfy
∥ p − q ∥ 2 ≥ V + ∥ q − o ∥ 2 . (1) \lVert p-q\rVert^2\ge V+\lVert q-o\rVert^2. \tag*{(1)} ∥ p − q ∥ 2 ≥ V + ∥ q − o ∥ 2 . (1) After a a a deletions, each count is at least α m − a \alpha m-a α m − a , simultaneously for all q q q . Insertions preserve these lower bounds.
Proof. Write ( x , r ) (x,r) ( x , r ) for a point of the lifted space. Consider the closed halfspace H c o r e = { ( x , r ) : r − 2 ⟨ o , x ⟩ ≤ s − 2 ∥ o ∥ 2 } H_{\mathrm{core}}=\{(x,r):r-2\langle o,x\rangle\le s-2\lVert o\rVert^2\} H core = {( x , r ) : r − 2 ⟨ o , x ⟩ ≤ s − 2 ∥ o ∥ 2 } . Its boundary contains z = ( o , s ) z=(o,s) z = ( o , s ) . For a lifted input point, membership is equivalent to ∥ p − o ∥ 2 ≤ s − ∥ o ∥ 2 = V \lVert p-o\rVert^2\le s-\lVert o\rVert^2=V ∥ p − o ∥ 2 ≤ s − ∥ o ∥ 2 = V . Depth therefore gives the core count.
For a fixed query q q q , use the other closed halfspace H q = { ( x , r ) : r − 2 ⟨ q , x ⟩ ≥ s − 2 ⟨ q , o ⟩ } H_q=\{(x,r):r-2\langle q,x\rangle\ge s-2\langle q,o\rangle\} H q = {( x , r ) : r − 2 ⟨ q , x ⟩ ≥ s − 2 ⟨ q , o ⟩} . Its boundary also contains z z z . Adding ∥ q ∥ 2 \lVert q\rVert^2 ∥ q ∥ 2 to the inequality for p + p^+ p + gives ∥ p − q ∥ 2 ≥ s − 2 ⟨ q , o ⟩ + ∥ q ∥ 2 = V + ∥ q − o ∥ 2 \lVert p-q\rVert^2\ge s-2\langle q,o\rangle+\lVert q\rVert^2=V+\lVert q-o\rVert^2 ∥ p − q ∥ 2 ≥ s − 2 ⟨ q , o ⟩ + ∥ q ∥ 2 = V + ∥ q − o ∥ 2 . Depth gives at least α m \alpha m α m such points. This holds for every halfspace H q H_q H q , not just for a fixed list of queries. A deletion removes at most one point from each counted set; an insertion removes none. The simultaneous survival statement follows deterministically. □
Computing the certificate. Finding a point of high halfspace depth is a separate algorithmic problem; taking the ordinary centroid does not give the required depth. In the arithmetic model, the Har-Peled–Jones constructor [20 Theorem 18] , applied in dimension d + 1 d+1 d + 1 , gives α = 1 / [ 4 ( d + 3 ) 2 ] \alpha=1/[4(d+3)^2] α = 1/ [ 4 ( d + 3 ) 2 ] with failure probability φ \varphi φ in O ( ( d + 1 ) 7 log 3 ( d + 2 ) log 3 ( 2 / φ ) ) O((d+1)^7\log^3(d+2)\log^3(2/\varphi)) O (( d + 1 ) 7 log 3 ( d + 2 ) log 3 ( 2/ φ )) arithmetic operations, given uniform sampling access to the birth pool. For rational coordinates, Appendix § 11 gives an exact sampled linear program with a depth parameter satisfying α − 1 = poly ( d , log ( 1 / φ ) ) \alpha^{-1}=\operatorname{poly}(d,\log(1/\varphi)) α − 1 = poly ( d , log ( 1/ φ )) and running time poly ( d , B , log ( 1 / φ ) ) \operatorname{poly}(d,B,\log(1/\varphi)) poly ( d , B , log ( 1/ φ )) . This avoids an assumption of strongly polynomial linear programming.
For zero error, the same appendix constructs at least β m \beta m β m pairwise disjoint blocks, each containing at most s 0 = poly ( d ) s_0=\operatorname{poly}(d) s 0 = poly ( d ) birth points, with β − 1 = poly ( d ) \beta^{-1}=\operatorname{poly}(d) β − 1 = poly ( d ) . It supplies exact convex coefficients expressing the same z z z in the lifted convex hull of every block. All coefficients and the core size are checked before a construction is accepted. The expected construction time is m poly ( d , B ) m\operatorname{poly}(d,B) m poly ( d , B ) .
The current node and its residual. During a node’s lifetime, let S S S denote its current input. Its core is C = S ∩ B ( o , V ) C=S\cap B(o,\sqrt{V}) C = S ∩ B ( o , V ) , and its child receives exactly S ∖ C S\setminus C S ∖ C . The center and V V V stay fixed until replacement. We permit at most α m / 16 \alpha m/16 α m /16 changes to the node’s input. Lemma 5.1 then leaves at least 15 α m / 16 15\alpha m/16 15 α m /16 birth points in the current core, while ∣ S ∣ ≤ ( 1 + α / 16 ) m |S|\le(1+\alpha/16)m ∣ S ∣ ≤ ( 1 + α /16 ) m . Thus the child is smaller than the input by a factor 1 − Ω ( α ) 1-\Omega(\alpha) 1 − Ω ( α ) . Repeating this operation gives O ( α − 1 log ( n + 1 ) ) O(\alpha^{-1}\log(n+1)) O ( α − 1 log ( n + 1 )) nodes and ends in a leaf of polynomial size, where all distances can be checked exactly. In the certified version the lifetime is set by β \beta β instead. The replacement schedule in § 7 enforces these lifetime bounds, including while new nodes are being constructed.
Maintaining the baseline pair. A balanced search tree stores the current squared radii ∥ p − o ∥ 2 \lVert p-o\rVert^2 ∥ p − o ∥ 2 for p ∈ S p\in S p ∈ S . Let y y y be a point with maximum radius R S = max p ∈ S ∥ p − o ∥ R_S=\max_{p\in S}\lVert p-o\rVert R S = max p ∈ S ∥ p − o ∥ . We maintain an actual current pair whose length L L L satisfies
L 2 ≥ V + R S 2 . (2) L^2\ge V+R_S^2. \tag*{(2)} L 2 ≥ V + R S 2 . (2)
In the Monte Carlo construction, draw O ( α − 1 log ( 1 / ψ ) ) O(\alpha^{-1}\log(1/\psi)) O ( α − 1 log ( 1/ ψ )) fresh uniform samples from S S S and take the farthest sampled point from y y y . Conditional on the entire history and a valid center, at least an α / 2 \alpha/2 α /2 fraction of S S S satisfies (1) with q = y q=y q = y . Hence the sample fails with probability at most ψ \psi ψ . The point y y y may depend on every earlier random choice: the sampling is performed after y y y is fixed. Subtree sizes in the membership tree support uniform rank sampling.
In the zero-error construction, choose any certificate block whose points all remain active. Its exact coefficients give, for every q q q ,
∑ p λ p ∥ p − q ∥ 2 = ∥ q − o ∥ 2 + V . (3) \sum_p \lambda_p \lVert p-q\rVert^2 = \lVert q-o\rVert^2 + V. \tag*{(3)} p ∑ λ p ∥ p − q ∥ 2 = ∥ q − o ∥ 2 + V . (3)
Scanning that block finds a point whose squared distance is at least this weighted average. A deletion invalidates at most one block because the blocks are disjoint, so an intact block remains throughout the permitted lifetime. A linked list of intact blocks and one block pointer per birth identity suffice for the bookkeeping.
The next lemma completes the geometric part of the endpoint result. Its proof assigns a diametral pair to one node, where the triangle inequality and (2) give the entire approximation factor.
Lemma 5.2 (A 2 \sqrt{2} 2 -approximate diameter pair). If every current node satisfies (2) , the longest of its baseline pairs and the exact leaf pair has length in [ diam ( P ) / 2 , diam ( P ) ] [\operatorname{diam}(P)/\sqrt{2},\operatorname{diam}(P)] [ diam ( P ) / 2 , diam ( P )] .
Proof. Choose x , y ∈ P x,y \in P x , y ∈ P with ∥ x − y ∥ = diam ( P ) \lVert x-y\rVert= \operatorname{diam}(P) ∥ x − y ∥ = diam ( P ) . If both reach the leaf, the leaf’s exact pair has this length. Otherwise let node i i i be the first node whose core contains either endpoint, say x x x . Both endpoints still belong to its input S i S_i S i : neither was removed by an earlier core. Hence ∥ x − o i ∥ ≤ V i \lVert x-o_i\rVert\le\sqrt{V_i} ∥ x − o i ∥ ≤ V i and ∥ y − o i ∥ ≤ R S i \lVert y-o_i\rVert\le R_{S_i} ∥ y − o i ∥ ≤ R S i . Therefore
diam ( P ) ≤ V i + R S i ≤ 2 V i + R S i 2 ≤ 2 L i . \operatorname{diam}(P) \le\sqrt{V_i}+R_{S_i} \le\sqrt{2}\sqrt{V_i+R_{S_i}^{2}} \le\sqrt{2}L_i. diam ( P ) ≤ V i + R S i ≤ 2 V i + R S i 2 ≤ 2 L i .
The middle inequality follows from ( a + b ) 2 ≤ 2 ( a 2 + b 2 ) (a+b)^2 \le2(a^2+b^2) ( a + b ) 2 ≤ 2 ( a 2 + b 2 ) . Every candidate is a pair of active points, so its length is at most diam ( P ) \operatorname{diam}(P) diam ( P ) . Before exposing the answer after an update, refresh every affected node; in particular no deleted endpoint remains in a stored pair.
We keep two distinct active identifiers as a fallback when the maximum stored distance is zero. With fewer than two active points we use the zero-diameter convention. Thus coincident coordinates do not force an output to repeat one identifier.
Restricting the radii and distance scales
To obtain a factor c < 2 c < \sqrt{2} c < 2 , we must improve the estimate of D C = max x ∈ C , y ∈ S ∥ x − y ∥ D_C = \max_{x\in C,y\in S}\lVert x-y\rVert D C = max x ∈ C , y ∈ S ∥ x − y ∥ at each node. Set D C = 0 D_C=0 D C = 0 if C C C is empty. The baseline already handles points very far from the center. This permits a fixed local radial grid, independent of the coordinate spread and of later deletions.
Fix 1 < c < 2 1<c<\sqrt{2} 1 < c < 2 and choose rational ε > 0 \varepsilon>0 ε > 0 , γ > 1 \gamma>1 γ > 1 , and λ > 1 \lambda>1 λ > 1 such that
κ = γ + 2 ε < c , κ λ < c , K ∈ Z , K ≥ 2 / ( c − 1 ) . \kappa=\gamma+2\varepsilon<c,\qquad\kappa\lambda<c,\qquad K\in\mathbb{Z},\qquad K\ge2/(c-1). κ = γ + 2 ε < c , κλ < c , K ∈ Z , K ≥ 2/ ( c − 1 ) .
The parameter ε \varepsilon ε controls radial rounding, γ \gamma γ separates the strong and weak distance thresholds, and λ \lambda λ is the ratio between consecutive distance scales. § 9 gives concrete choices.
Lemma 5.3 (Distances outside the local range). If V = 0 V=0 V = 0 or R S > K V R_S>K\sqrt{V} R S > K V , then D C < c L D_C<cL D C < c L unless $D_C=L=0.
Proof. For V = 0 V=0 V = 0 , every core point equals o o o , so D C ≤ R S ≤ L D_C \le R_S \le L D C ≤ R S ≤ L . For R S > K V R_S > K\sqrt{V} R S > K V , the triangle inequality gives
D C ≤ V + R S < ( 1 + 1 / K ) R S < c L , D_C \le\sqrt{V} + R_S < (1+1/K)R_S < cL, D C ≤ V + R S < ( 1 + 1/ K ) R S < c L ,
because 1 + 1 / K < c 1+1/K < c 1 + 1/ K < c and R S ≤ L R_S \le L R S ≤ L .
Accordingly, the local search structures include on their right side only points of radius at most K V K\sqrt{V} K V . If an outlier is present, the baseline suffices. When the last outlier is deleted, every remaining point is already in the local structures.
Assume now V > 0 V>0 V > 0 , and put m 0 = ⌈ 1 / e ⌉ m_0=\lceil1/e\rceil m 0 = ⌈ 1/ e ⌉ . The fixed shell radii are r j = ( j / m 0 ) V r_j=(j/m_0)\sqrt{V} r j = ( j / m 0 ) V for 0 ≤ j ≤ K m 0 0\le j\le Km_0 0 ≤ j ≤ K m 0 . Round each eligible point inward to the largest radius no greater than its own, and write the rounded point as p ~ \tilde{p} p ~ . The displacement is at most e V e\sqrt{V} e V . We store only the original point and its shell number: comparisons of m 0 2 ∥ p − o ∥ 2 m_0^2\lVert p-o\rVert^2 m 0 2 ∥ p − o ∥ 2 with j 2 V j^2V j 2 V determine the shell exactly.
Use distance scales R ℓ = λ ℓ V / 2 R_\ell=\lambda^\ell\sqrt{V}/2 R ℓ = λ ℓ V /2 for 0 ≤ ℓ ≤ J 0\le\ell\le J 0 ≤ ℓ ≤ J , where J J J is the first index with λ J / 2 ≥ K + 1 \lambda^J/2\ge K+1 λ J /2 ≥ K + 1 . A configuration is a triple ( j , k , ℓ ) (j,k,\ell) ( j , k , ℓ ) of a positive core shell, a positive input shell, and a distance scale. Retain it only if
r j 2 + r k 2 ≤ R ℓ 2 , γ R ℓ ≤ r j + r k . (4) r_j^2+r_k^2\le R_\ell^2,\qquad\gamma R_\ell\le r_j+r_k. \tag*{(4)} r j 2 + r k 2 ≤ R ℓ 2 , γ R ℓ ≤ r j + r k . (4)
Its left vertices are copies of the core points in shell j j j ; its right vertices are copies of the eligible input points in shell k k k . A weak edge has rounded distance greater than R ℓ R_\ell R ℓ . A strong edge has rounded distance greater than γ R ℓ \gamma R_\ell γ R ℓ and is therefore also weak.
For nonzero directions u p = ( p − o ) / ∥ p − o ∥ u_p=(p-o)/\lVert p-o\rVert u p = ( p − o ) / ∥ p − o ∥ , the identity ∥ x ~ − y ~ ∥ 2 = r j 2 + r k 2 + 2 r j r k ⟨ − u x , u y ⟩ \lVert\tilde{x}-\tilde{y}\rVert^2=r_j^2+r_k^2+2r_jr_k\langle-u_x,u_y\rangle ∥ x ~ − y ~ ∥ 2 = r j 2 + r k 2 + 2 r j r k ⟨ − u x , u y ⟩ turns distance into correlation. Define
a = γ 2 R ℓ 2 − r j 2 − r k 2 2 r j r k , b = R ℓ 2 − r j 2 − r k 2 2 r j r k . a=\frac{\gamma^2R_\ell^2-r_j^2-r_k^2}{2r_jr_k},\qquad b=\frac{R_\ell^2-r_j^2-r_k^2}{2r_jr_k}. a = 2 r j r k γ 2 R ℓ 2 − r j 2 − r k 2 , b = 2 r j r k R ℓ 2 − r j 2 − r k 2 .
Then strong edges have correlation greater than a a a , and the exact weak-edge test is ⟨ − u x , u y ⟩ > b \langle-u_x,u_y\rangle>b ⟨ − u x , u y ⟩ > b . All factors of V V V cancel, so a , b a,b a , b are rational numbers fixed when the configuration is created. With g = γ 2 − 1 g=\gamma^2-1 g = γ 2 − 1 , eligibility gives
0 ≤ b < a ≤ 1 , a − ( 1 + g ) b = g r j 2 + r k 2 2 r j r k > g . (5) 0\le b<a\le1,\qquad a-(1+g)b=g\frac{r_j^2+r_k^2}{2r_jr_k}>g. \tag*{(5)} 0 ≤ b < a ≤ 1 , a − ( 1 + g ) b = g 2 r j r k r j 2 + r k 2 > g . (5)
Maintaining one witness at each scale
An angular query returns a verified weak neighbor whenever a strong neighbor exists. It may also return a weak neighbor in the absence of a strong one. Such a search operation does not, by itself, maintain a diameter pair after deletions. A matching supplies the missing invariant with only a constant number of searches per membership change.
For a configuration, let V L , V R V_L,V_R V L , V R be its active vertex sets and E w e a k , E s t r o n g E_{\mathrm{weak}},E_{\mathrm{strong}} E weak , E strong its two edge sets. Maintain a matching M M M , and let U L , U R U_L,U_R U L , U R be the unmatched vertices on the two sides. The invariant is
M ⊆ E w e a k is a matching , E s t r o n g ∩ ( U L × U R ) = ∅ . M\subseteq E_{\mathrm{weak}}\text{ is a matching},\qquad E_{\mathrm{strong}}\cap(U_L\times U_R)=\varnothing. M ⊆ E weak is a matching , E strong ∩ ( U L × U R ) = ∅ .
Each unmatched set has an angular index. The birth-pool guarantees of the next section hold for all later subsets and queries, and § 7 permits fully dynamic membership changes. Thus these searches remain valid even when matching repairs depend on exposed earlier randomness.
To verify the invariant, consider ATTACH. If it finds a weak edge, removing the two endpoints from the unmatched sets cannot create a strong edge between those sets. If it finds none, the query Algorithm 2 Maintaining one local matching
Attach (v v v ): v v v is active, unmatched, and absent from its unmatched index.
Search the opposite unmatched index in direction − u v -u_v − u v , accepting exactly correlations > b > b > b .
if a neighbor w w w is returned then
Remove w w w from its unmatched index; insert edge v w vw v w in M M M and record its exact squared distance.
else
Insert v v v into its unmatched index with a fresh insertion lifetime.
end if
InsertOriginal (p p p ):
Create its applicable left and right copies, in that order, and call Attach on each.
DeleteOriginal (p p p ):
Remove both copies of p p p from their unmatched indices or matching edges.
Collect the surviving former partners in F F F ; call Attach on each still-unmatched member of F F F .
StoredEdge (): return the first edge in the matching list, or empty.
promise ensures that the newly unmatched vertex has no strong neighbor in the opposite unmatched set. Deleting an unmatched vertex preserves the invariant. Deleting a matched vertex makes only its former partner newly unmatched, which Attach handles. An original point has at most two copies, so ∣ F ∣ ≤ 2 |F| \le2 ∣ F ∣ ≤ 2 . We remove both before repairing either partner. A self-edge between two copies of one identity has rounded distance zero and cannot pass the weak test.
An empty matching certifies that the configuration has no strong edge. A nonempty matching supplies an actual current pair from any one of its weak edges. For the node, let W W W be the maximum of the baseline length L L L and the original lengths of one stored edge from each nonempty matching. The next lemma explains why inward rounding does not invalidate an old edge when the baseline decreases.
Lemma 5.4 (Radial rounding preserves a distance witness). For any indexed identities x , y x, y x , y ,
∥ x ~ − y ~ ∥ ≤ max { ∥ x − y ∥ , ∥ x − o ∥ , ∥ y − o ∥ } ≤ max { ∥ x − y ∥ , L } . \lVert\tilde{x} - \tilde{y} \rVert\le\max\{\lVert x-y\rVert,\lVert x-o\rVert,\lVert y-o\rVert\} \le\max\{\lVert x-y\rVert,L\}. ∥ x ~ − y ~ ∥ ≤ max {∥ x − y ∥ , ∥ x − o ∥ , ∥ y − o ∥} ≤ max {∥ x − y ∥ , L } . In particular, a current weak edge at scale R ℓ R_\ell R ℓ implies W > R ℓ W > R_\ell W > R ℓ .
Proof. Inward rounding means x ~ = ξ x + ( 1 − ξ ) o \tilde{x} = \xi x + (1-\xi)o x ~ = ξ x + ( 1 − ξ ) o and y ~ = υ y + ( 1 − υ ) o \tilde{y} = \upsilon y + (1-\upsilon)o y ~ = υ y + ( 1 − υ ) o for ξ , υ ∈ [ 0 , 1 ] \xi,\upsilon\in[0,1] ξ , υ ∈ [ 0 , 1 ] . Subtracting gives
x ~ − y ~ = ξ υ ( x − y ) + ξ ( 1 − υ ) ( x − o ) + ( 1 − ξ ) υ ( o − y ) . \tilde{x} - \tilde{y} = \xi\upsilon(x-y) + \xi(1-\upsilon)(x-o) + (1-\xi)\upsilon(o-y). x ~ − y ~ = ξ υ ( x − y ) + ξ ( 1 − υ ) ( x − o ) + ( 1 − ξ ) υ ( o − y ) . The three coefficients are nonnegative and sum to at most one. The triangle inequality proves the first bound. Both radii are at most the current R S ≤ L R_S \le L R S ≤ L , proving the second. A weak edge has rounded length greater than R ℓ R_\ell R ℓ , so either its original length or the current baseline is greater than R ℓ R_\ell R ℓ .
We can now show that some maintained scale detects every core–input distance that is too long for the baseline. The gaps between c c c , κ \kappa κ , and γ \gamma γ pay, respectively, for scale rounding and radial rounding.
Lemma 5.5 (The local diameter guarantee). If the baseline and angular searches satisfy their promises, then D C / c ≤ W ≤ diam ( S ) D_C/c \le W \le\operatorname{diam}(S) D C / c ≤ W ≤ diam ( S ) .
Proof. If V = 0 V = 0 V = 0 , an outlier is present, or D C ≤ c L D_C \le cL D C ≤ c L , the baseline suffices by Lemma 5.3 . Otherwise V > 0 V > 0 V > 0 , R S ≤ K V R_S \le K\sqrt{V} R S ≤ K V , and D C > c L D_C > cL D C > c L .
Choose the grid scale immediately below D C / κ D_C/\kappa D C / κ , taking the predecessor when this value is itself on the grid. It satisfies
R ℓ < D C / κ ≤ λ R ℓ , R ℓ ≥ D C / ( κ λ ) > D C / c > L . R_\ell< D_C/\kappa\le\lambda R_\ell,\qquad R_\ell\ge D_C/(\kappa\lambda) > D_C/c > L. R ℓ < D C / κ ≤ λ R ℓ , R ℓ ≥ D C / ( κλ ) > D C / c > L .
Such a scale exists because the grid starts at V / 2 \sqrt{V}/2 V /2 , while D C > c V D_C > c\sqrt{V} D C > c V , and ends at or above ( K + 1 ) V ≥ D C (K+1)\sqrt{V} \ge D_C ( K + 1 ) V ≥ D C .
Let x ∈ C , y ∈ S x \in C,y \in S x ∈ C , y ∈ S realize D C D_C D C . Rounding both radii loses at most 2 e V < 2 e R ℓ 2e\sqrt{V}<2eR_\ell 2 e V < 2 e R ℓ . The rounded distance is therefore greater than ( κ − 2 e ) R ℓ = γ R ℓ (\kappa-2e)R_\ell= \gamma R_\ell ( κ − 2 e ) R ℓ = γ R ℓ . Neither rounded radius is zero, since then the rounded distance would be at most R S ≤ L < R ℓ R_S \le L < R_\ell R S ≤ L < R ℓ . If their shells are j , k j,k j , k , then r j 2 + r k 2 ≤ V + R S 2 ≤ L 2 < R ℓ 2 r_j^2+r_k^2 \le V+R_S^2 \le L^2<R_\ell^2 r j 2 + r k 2 ≤ V + R S 2 ≤ L 2 < R ℓ 2 ; their rounded distance is at most r j + r k r_j+r_k r j + r k . These two facts establish eligibility in (4) .
The configuration contains the strong edge x y xy x y , so its matching is nonempty. Lemma 5.4 yields W > R ℓ > D C / c W > R_\ell> D_C/c W > R ℓ > D C / c . Every stored candidate is an actual current pair, proving the upper bound. □
The first-core argument from Lemma 5.2 now proves the global factor-c c c guarantee. Each point update causes only constantly many angular operations per applicable configuration. When a pending node scans a point, it completes both matching copies, the point’s child membership, and its processed flag within one external update. § 7 specifies how these scans include insertions and deletions arriving during construction.
One angular gap for all configurations
Recall the inequality a − ( 1 + g ) b ≥ g a-(1+g)b \ge g a − ( 1 + g ) b ≥ g in (5) , where g = γ 2 − 1 g=\gamma^2-1 g = γ 2 − 1 . It permits the same search exponent for every shell pair: data directions u u u and query directions z z z can be padded so that correlations above a a a become at least g g g , whereas correlations at most b b b become nonpositive. Formally, padding by ( u , b ) / 1 + b (u,\sqrt{b})/\sqrt{1+b} ( u , b ) / 1 + b and ( z , − b ) / 1 + b (z,-\sqrt{b})/\sqrt{1+b} ( z , − b ) / 1 + b changes correlation r r r into ( r − b ) / ( 1 + b ) (r-b)/(1+b) ( r − b ) / ( 1 + b ) . We use rational padding with a small margin to accommodate rounding of queries.
Lemma 5.6 (A common angular gap). Assume (5) and let 0 < e ≤ g / 16 0<e\le g/16 0 < e ≤ g /16 be rational. One can compute rational A > 0 A>0 A > 0 , B ≥ 0 B\ge0 B ≥ 0 with A 2 + B 2 = 1 A^2+B^2=1 A 2 + B 2 = 1 such that, for unit vectors u , z , z ^ u,z,\hat{z} u , z , z ^ with ∥ z ^ − z ∥ ≤ e / 8 \lVert\hat{z}-z\rVert\le e/8 ∥ z ^ − z ∥ ≤ e /8 , the padded correlation ⟨ ( A z ^ , − B ) , ( A u , B ) ⟩ \langle(A\hat{z},-B),(Au,B)\rangle ⟨( A z ^ , − B ) , ( A u , B )⟩ is at least h = g − 11 e h=g-11e h = g − 11 e when ⟨ z , u ⟩ ≥ a \langle z,u\rangle\ge a ⟨ z , u ⟩ ≥ a , and is negative when ⟨ z , u ⟩ ≤ b \langle z,u\rangle\le b ⟨ z , u ⟩ ≤ b . The computation is polynomial in the bit length of b b b and log ( 1 / e ) \log(1/e) log ( 1/ e ) .
Proof. Use the rational parametrization A = ( 1 − v 2 ) / ( 1 + v 2 ) A=(1-v^2)/(1+v^2) A = ( 1 − v 2 ) / ( 1 + v 2 ) , B = 2 v / ( 1 + v 2 ) B=2v/(1+v^2) B = 2 v / ( 1 + v 2 ) . Choose v ∈ [ 0 , 1 / 2 ] ∩ Q v\in[0,1/2]\cap\mathbb{Q} v ∈ [ 0 , 1/2 ] ∩ Q so that B 2 / A 2 ∈ [ b + 4 e , b + 5 e ] B^2/A^2\in[b+4e,b+5e] B 2 / A 2 ∈ [ b + 4 e , b + 5 e ] . The function 4 v 2 / ( 1 − v 2 ) 2 4v^2/(1-v^2)^2 4 v 2 / ( 1 − v 2 ) 2 is increasing on this interval, has derivative at most 12, and exceeds 1 at v = 1 / 2 v=1/2 v = 1/2 . Moreover b ≤ 1 − g b\le1-g b ≤ 1 − g and 5 e ≤ 5 g / 16 5e\le5g/16 5 e ≤ 5 g /16 , so the target interval lies below 1. Binary search on a rational mesh of spacing at most e / 16 e/16 e /16 therefore finds a suitable v v v .
Write Δ = B 2 / A 2 − b ∈ [ 4 e , 5 e ] \Delta=B^2/A^2-b\in[4e,5e] Δ = B 2 / A 2 − b ∈ [ 4 e , 5 e ] . Before rounding z z z , a correlation r r r becomes ( r − b − Δ ) / ( 1 + b + Δ ) (r-b-\Delta)/(1+b+\Delta) ( r − b − Δ ) / ( 1 + b + Δ ) . For r ≤ b r\le b r ≤ b this is at most − 2 e -2e − 2 e , because 1 + b + Δ < 2 1+b+\Delta<2 1 + b + Δ < 2 . For r ≥ a r\ge a r ≥ a , the premise gives a lower bound g − ( 1 + g ) Δ / ( 1 + b + Δ ) ≥ g − 10 e g-(1+g)\Delta/(1+b+\Delta)\ge g-10e g − ( 1 + g ) Δ/ ( 1 + b + Δ ) ≥ g − 10 e . Replacing z z z by z ^ \hat{z} z ^ changes the padded correlation by at most e / 8 e/8 e /8 . Both asserted inequalities follow. □
Queries and exact comparisons. Use a normalized lattice net of radius e / 8 e/8 e /8 in the original direction space. Its logarithmic cardinality is O ( d log ( d / e ) ) O(d\log(d/e)) O ( d log ( d / e )) ; it is used for the analysis and never enumerated. Round each query before padding, but continue to accept candidates by the original test ⟨ z , u ⟩ > b \langle z,u\rangle> b ⟨ z , u ⟩ > b . Thus every rejected candidate has negative padded correlation, exactly the separation required by the two search structures in the next section.
For rational coordinates, normalization does not require storing irrational coordinates. For a raw vector w w w , a cap comparison has the form A ⟨ G 1 : d , w ⟩ ≥ ( a 0 − B G d + 1 ) ∥ w ∥ A\langle G_{1:d},w\rangle\ge(a_0-BG_{d+1})\lVert w\rVert A ⟨ G 1 : d , w ⟩ ≥ ( a 0 − B G d + 1 ) ∥ w ∥ . Testing the signs and then the squares decides it exactly. Section 9 chooses γ = c − O ( ϵ ) \gamma=c-O(\epsilon) γ = c − O ( ϵ ) , λ = 1 + ϵ / ( 4 κ ) \lambda=1+\epsilon/(4\kappa) λ = 1 + ϵ / ( 4 κ ) , K = ⌈ 2 / ( c − 1 ) ⌉ K=\lceil2/(c-1)\rceil K = ⌈ 2/ ( c − 1 )⌉ , and ϵ = Θ c ( 1 / log ( 2 n ) ) \epsilon=\Theta_c(1/\log(2n)) ϵ = Θ c ( 1/ log ( 2 n )) . There are O c ( log n ) O_c(\log n) O c ( log n ) shells and scales and O c ( log 3 n ) O_c(\log^3 n) O c ( log 3 n ) configurations per node. Their common good correlation is h = c 2 − 1 − O c ( 1 / log n ) h=c^2-1-O_c(1/\log n) h = c 2 − 1 − O c ( 1/ log n ) , which preserves the exact powers of n n n in the explicit-filter bounds.
Angular search: explicit lists and implicit incidences
The preceding section reduces each local distance search to a single problem on unit vectors: find a point whose inner product with the query is positive whenever some point has inner product at least a fixed h > 0 h>0 h > 0 . This section gives two implementations. Explicit lists prove the balanced bound with exact powers of n n n . A second implementation certifies that no target can be missed and stores point–filter memberships implicitly; it yields the improved bound near linear space. We first establish coverage and query costs, then account for construction and deletions.
The search interface. A generation is an index constructed on a fixed set P 0 P_0 P 0 of m m m unit vectors. The set is fixed before this generation’s random choices, and later operations may delete its members. A query supplies a unit vector z z z and an exact acceptance test in the original geometry. A target is a current point p p p with ⟨ p , z ⟩ ≥ h \langle p,z\rangle\ge h ⟨ p , z ⟩ ≥ h . The test is compatible if every rejected point satisfies ⟨ p , z ⟩ ≤ 0 \langle p,z\rangle\le0 ⟨ p , z ⟩ ≤ 0 ; the certified construction uses the stronger bound ⟨ p , z ⟩ ≤ − δ \langle p,z\rangle\le-\delta ⟨ p , z ⟩ ≤ − δ for a specified δ > 0 \delta>0 δ > 0 . Thus every target must be accepted. The required answer is an accepted current identity, or None when the search finds none. On its correctness event, None implies that no target exists. Query directions have already been rounded before the common-gap lift, using its reserved error margin.
The two search exponents. The parameter x ∈ [ h , 1 ] x\in[h,1] x ∈ [ h , 1 ] controls the relative thresholds for data and queries. Define
I h ( x ) = 1 + x 2 − 2 h x 1 − h 2 , u = I h ( x ) − 1 = ( x − h ) 2 1 − h 2 , q = I h ( x ) − x 2 = ( 1 − h x ) 2 1 − h 2 . I_h(x)=\frac{1+x^2-2hx}{1-h^2},\qquad u=I_h(x)-1=\frac{(x-h)^2}{1-h^2},\qquad q=I_h(x)-x^2=\frac{(1-hx)^2}{1-h^2}. I h ( x ) = 1 − h 2 1 + x 2 − 2 h x , u = I h ( x ) − 1 = 1 − h 2 ( x − h ) 2 , q = I h ( x ) − x 2 = 1 − h 2 ( 1 − h x ) 2 .
The meaning of these quantities is as follows: a point belongs to roughly m u m^u m u filters, and a query examines roughly m q m^q m q filter labels and rejected occurrences. The next lemma records the resulting curve and an inequality needed to pay for updates.
Lemma 6.1 (The angular tradeoff). As x x x ranges from h h h to 1 1 1 , u u u ranges from 0 0 0 to ρ h = ( 1 − h ) / ( 1 + h ) \rho_h=(1-h)/(1+h) ρ h = ( 1 − h ) / ( 1 + h ) , and
q = q h ( u ) = ( 1 − h 2 − h u ) 2 . q=q_h(u)=\left(\sqrt{1-h^2}-h\sqrt{u}\right)^2. q = q h ( u ) = ( 1 − h 2 − h u ) 2 . Moreover,
q − u = 1 − x 2 ≥ 0. q-u=1-x^2\ge0. q − u = 1 − x 2 ≥ 0. Proof. From the formula for u u u , x = h + u ( 1 − h 2 ) x=h+\sqrt{u(1-h^2)} x = h + u ( 1 − h 2 ) . Substitution into the expression for q q q gives the curve. The endpoint x = 1 x=1 x = 1 gives u = ( 1 − h ) / ( 1 + h ) u=(1-h)/(1+h) u = ( 1 − h ) / ( 1 + h ) . Finally, subtracting u = I h ( x ) − 1 u=I_h(x)-1 u = I h ( x ) − 1 from q = I h ( x ) − x 2 q=I_h(x)-x^2 q = I h ( x ) − x 2 gives the last identity.
Throughout this section, P \mathcal{P} P denotes a polynomial factor of fixed degree in dimension, input precision, and the stated logarithmic parameters. Fixed accuracy parameters may affect its coefficients. All powers of the pool size m m m are displayed explicitly.
Explicit filter lists
A filter is a bucket label defined by a random direction. A point is stored under that label when its projection exceeds a threshold; a query visits the label when its own projection exceeds a possibly different threshold. The two thresholds let us reduce point replication at the cost of more query work. This is the asymmetric Gaussian filtering approach of Christiani [14 ] .
Let G G G be a standard Gaussian vector and let t ≥ 1 t \ge1 t ≥ 1 . The data test is ⟨ G , p ⟩ ≥ t \langle G,p\rangle\ge t ⟨ G , p ⟩ ≥ t , and the query test is ⟨ G , z ⟩ ≥ x t \langle G,z\rangle\ge xt ⟨ G , z ⟩ ≥ x t . Write p u , p q p_u,p_q p u , p q for their marginal probabilities, p 1 p_1 p 1 for a lower bound on their joint probability when ⟨ p , z ⟩ ≥ h \langle p,z\rangle\ge h ⟨ p , z ⟩ ≥ h , and p 2 p_2 p 2 for an upper bound when ⟨ p , z ⟩ ≤ 0 \langle p,z\rangle\le0 ⟨ p , z ⟩ ≤ 0 .
Lemma 6.2 (Gaussian filter probabilities). For h ≤ x ≤ 1 h \le x \le1 h ≤ x ≤ 1 and t ≥ 1 t \ge1 t ≥ 1 ,
p u ≤ e − t 2 / 2 , p q ≤ e − x 2 t 2 / 2 , p 1 ≥ c h t − 2 e − I h ( x ) t 2 / 2 , p 2 ≤ e − ( 1 + x 2 ) t 2 / 2 . p_u \le e^{-t^2/2},\qquad p_q \le e^{-x^2t^2/2},\qquad p_1 \ge c_h t^{-2}e^{-I_h(x)t^2/2},\qquad p_2 \le e^{-(1+x^2)t^2/2}. p u ≤ e − t 2 /2 , p q ≤ e − x 2 t 2 /2 , p 1 ≥ c h t − 2 e − I h ( x ) t 2 /2 , p 2 ≤ e − ( 1 + x 2 ) t 2 /2 . where c h > 0 c_h > 0 c h > 0 can be chosen uniformly when h h h stays in a compact subinterval of ( 0 , 1 ) (0,1) ( 0 , 1 ) .
Proof. The marginal estimates are the usual one-dimensional Gaussian tail bounds. For the lower bound, first take correlation exactly h h h . Integrate the bivariate density over [ t , t + 1 / t ] × [ x t , x t + 1 / t ] [t,t+1/t] \times[xt,xt+1/t] [ t , t + 1/ t ] × [ x t , x t + 1/ t ] . Its exponent at the lower corner is I h ( x ) t 2 / 2 I_h(x)t^2/2 I h ( x ) t 2 /2 , and the change in the exponent throughout this rectangle is bounded by a constant depending only on h h h . The rectangle has area t − 2 t^{-2} t − 2 , giving the stated lower bound. Gaussian joint upper-tail probabilities increase with correlation, so the same lower bound holds at every larger correlation. At nonpositive correlation the joint probability is at most its value for independent coordinates, giving p 2 p_2 p 2 by multiplying the two marginal bounds. These estimates also give computable conservative rational bounds for the implementation. □
We combine a fixed number ℓ \ell ℓ of independent base families. A full filter is a tuple containing one cap from each family. Evaluating the base lists avoids examining all tuples. Explicit caps on list length and search work give deterministic resource bounds; independent copies will supply the desired success probability.
Lemma 6.3 (A capped explicit index). Fix an integer ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 . A pool of size m m m admits an explicit index with data work ( m u + m I h ( x ) / ℓ ) P (m^u+m^{I_h(x)/\ell})\mathcal{P} ( m u + m I h ( x ) / ℓ ) P , query work ( m q + m I h ( x ) / ℓ ) P (m^q+m^{I_h(x)/\ell})\mathcal{P} ( m q + m I h ( x ) / ℓ ) P , and space ( m 1 + u + m I h ( x ) / ℓ ) P (m^{1+u}+m^{I_h(x)/\ell})\mathcal{P} ( m 1 + u + m I h ( x ) / ℓ ) P . These bounds hold on every outcome. For a fixed query and target, a copy succeeds with constant probability; the same event works for every later subset of the birth pool and every compatible exact acceptance predicate.
Proof. Choose rational t ≥ 1 t \ge1 t ≥ 1 with ℓ t 2 / 2 = log ( 2 m ) + O ( 1 ) \ell t^2/2=\log(2m)+O(1) ℓ t 2 /2 = log ( 2 m ) + O ( 1 ) . Each of ℓ \ell ℓ independent base families contains M 0 = ⌈ log ( 100 ℓ ) / p 1 ⌉ M_0=\lceil\log(100\ell)/p_1\rceil M 0 = ⌈ log ( 100 ℓ ) / p 1 ⌉ caps. A full filter is a tuple of one cap from each family. Put A = M 0 ℓ A=M_0^\ell A = M 0 ℓ and
E u = A e − t 2 / 2 ≤ m u log O ( ℓ ) ( 2 m ) , E q = A e − x 2 t 2 / 2 ≤ m q log O ( ℓ ) ( 2 m ) . E_u=Ae^{-t^2/2}\le m^u\log^{O(\ell)}(2m),\qquad E_q=Ae^{-x^2t^2/2}\le m^q\log^{O(\ell)}(2m). E u = A e − t 2 /2 ≤ m u log O ( ℓ ) ( 2 m ) , E q = A e − x 2 t 2 /2 ≤ m q log O ( ℓ ) ( 2 m ) .
Compute a point’s eligible base lists first. If their product has more than 100 ( E u + 1 ) 100(E_u+1) 100 ( E u + 1 ) tuples, omit this point from this copy; otherwise store its tuples in buckets with exact deletion handles. Only nonempty buckets are allocated. A query similarly stops after 100 ( E q + 1 ) 100(E_q+1) 100 ( E q + 1 ) tuples or rejected occurrences. A candidate is tested before a stopping rule can discard it. The base-list computation costs ℓ M 0 ≤ m I h ( x ) / ℓ P \ell M_0 \le m^{I_h(x)/\ell}\mathcal{P} ℓ M 0 ≤ m I h ( x ) / ℓ P ; enumerating a Cartesian product is output sensitive. The expected point and query tuple counts are at most E u , E q E_u,E_q E u , E q . For a rejected birth point the shared-tuple probability is at most p 2 ℓ p_2^\ell p 2 ℓ , whence m A p 2 ℓ ≤ E q m A p_2^\ell\le E_q m A p 2 ℓ ≤ E q . A target shares a base cap in every family with probability at least 0.99. Markov’s inequality for the three caps leaves constant success probability. Here the three bad events are an overlong target list, an overlong query list, and too many shared occurrences with nonpositive-correlation birth points. On their complement, the target is stored and the search reaches it unless it has already returned an acceptable point. This argument counts potential rejected occurrences against all of P 0 P_0 P 0 . Every later subset and every compatible acceptance test rejects only occurrences in this same set. Thus one event works for all those choices; no monotonicity of the acceptance test is needed.
One event for all adaptive queries. A fixed-query success probability is insufficient when the random directions are exposed: an adversary could choose a later query that is unusually bad for those directions. We instead prove that the index succeeds simultaneously for a finite cover of all directions. To obtain this event, round the original unit direction to a normalized rational lattice of mesh η / ( 8 d ) \eta/(8\sqrt{d}) η / ( 8 d ) . Its error is at most η / 8 \eta/8 η /8 and its logarithmic cardinality is O ( d log ( d / η ) ) O(d\log(d/\eta)) O ( d log ( d / η )) . Only the chosen rounded point is computed. The common-gap lift reserves this error before specifying h h h and the rejected correlation. Amplify with O ( log ( m / ϵ 0 ) + d log ( d / η ) ) O(\log(m/\epsilon_0)+d\log(d/\eta)) O ( log ( m / ϵ 0 ) + d log ( d / η )) independent copies and union bound over the net and the m m m birth targets. The resulting event holds for every future query, every subset, and every compatible predicate, even after the seeds are exposed. This query-cover argument also appears in adversarially robust farthest neighbor search [11 ] ; here polynomial dimension dependence permits checking all copies.
Finite precision and exact exponents. The preceding argument uses ideal Gaussian variables only to analyze success probability. Finite Gaussian approximations preserve the event with polynomial precision. There are finitely many birth-vector and net comparisons; one-dimensional Gaussian anti-concentration bounds the chance that any ideal comparison lies in its rounding interval. A union bound only adds the logarithm of their number to the precision. Actual cap tests use signs and squared rational comparisons, and resource caps hold regardless of the coupling. § 9 chooses fixed ℓ ≥ 16 / ρ c \ell\ge16/\rho_c ℓ ≥ 16/ ρ c , where ρ c = 2 / c 2 − 1 \rho_c=2/c^2-1 ρ c = 2/ c 2 − 1 , and h = g c − O c ( 1 / log n ) h=g_c-O_c(1/\log n) h = g c − O c ( 1/ log n ) with g c = c 2 − 1 g_c=c^2-1 g c = c 2 − 1 , and x x x with u ≤ σ u\le\sigma u ≤ σ and q ≤ Q c ( σ ) + O c ( 1 / log n ) q\le Q_c(\sigma)+O_c(1/\log n) q ≤ Q c ( σ ) + O c ( 1/ log n ) . Thus the explicit update and space powers are exactly Q c ( σ ) Q_c(\sigma) Q c ( σ ) and 1 + σ 1+\sigma 1 + σ , with polynomial logarithmic factors.
Certified finite families
The explicit index may omit a target on an unlucky outcome. An always-correct search needs a finite test that certifies coverage of every target direction. We obtain such a test by decomposing the sphere into small-dimensional blocks, where an explicit finite net can be checked. The resulting product family can have many labels, but its description remains small. § 6.3 will store and search these labels without expanding their products.
A label identifies one filter; data and query labels use the same naming convention. Sharing a label makes a point a candidate, which must still pass the exact original acceptance test. Fix a negative rejection margin δ > 0 \delta>0 δ > 0 and a density parameter 0 < κ ≤ 1 0<\kappa\le1 0 < κ ≤ 1 . To control the number of labels and the number of rejected candidates separately, replace the threshold by
t 2 = 2 κ log m + O ( 1 ) . t^2 = 2\kappa\log m + O(1). t 2 = 2 κ log m + O ( 1 ) .
The pool still contains m m m points: in particular, an expected collision count must be summed over all m m m birth points, regardless of κ \kappa κ . The exponent allowance η > 0 \eta>0 η > 0 below pays for finite nets, splitting families, and exact representations. It may be made arbitrarily small for fixed accuracy parameters.
Proposition 6.4 (Certified angular labels). For every fixed η > 0 \eta> 0 η > 0 , a finite-word randomized constructor terminates almost surely and returns labels with the following guarantees. Every target pair shares a label on every accepted outcome. A fixed data point has expected label count at most m κ u + η P m^{\kappa_u+\eta}\mathcal{P} m κ u + η P ; a fixed query has expected routing work and label count at most m κ q + η P m^{\kappa_q+\eta}\mathcal{P} m κ q + η P ; and its expected shared-label occurrences with all birth points of correlation at most − δ -\delta − δ are at most
m 1 + κ ( q − 1 ) + η P . (6) m^{1+\kappa(q-1)+\eta}\mathcal{P}. \tag*{(6)} m 1 + κ ( q − 1 ) + η P . (6) The description size and workspace are at most m η P m^\eta\mathcal{P} m η P , and expected certification time is at most m η P m^\eta\mathcal{P} m η P . The full raw label universe has a deterministic size bound m κ ( 1 + u ) + η P m^{\kappa(1+u)+\eta}\mathcal{P} m κ ( 1 + u ) + η P . Its size and each label’s integer code can be computed without enumerating that universe.
Proof. The construction has three steps. First, an orthogonal decomposition puts every target into at least one moderate-dimensional block. Second, a finite splitting family reduces that block to small spheres. Third, checked cap families cover those spheres. We prove deterministic coverage first and then bound expected work. Exact finite certificates and arithmetic details appear in Appendix § 12 . Bounded m m m is handled by a scan. If d ≥ m d \ge m d ≥ m , scanning also costs only O ( d 2 ) O(d^2) O ( d 2 ) , so assume d < m d < m d < m . These scan cases are trivial single-label indices; their routing and rejected-occurrence counts are absorbed by the polynomial dimension factor or the fixed small-pool constant.
Preserving a target in one moderate block. Apply an exact rational orthogonal rotation and divide the padded space into blocks of dimension B 0 = Θ δ ( log m ) B_0 = \Theta_\delta(\log m) B 0 = Θ δ ( log m ) . Every positive-correlation pair survives in some normalized block, for every rotation: if all its nonzero block correlations were less than h h h , then
⟨ p , z ⟩ < h ∑ i ∥ p i ∥ ∥ z i ∥ ≤ h . \langle p,z\rangle< h\sum_i \lVert p_i\rVert\lVert z_i\rVert\le h. ⟨ p , z ⟩ < h i ∑ ∥ p i ∥ ∥ z i ∥ ≤ h .
For a fixed query, the negative margin ⟨ p , z ⟩ ≤ − δ \langle p,z\rangle\le-\delta ⟨ p , z ⟩ ≤ − δ leaves room for projection error. Concentration of the projected norms of p , z , p − z p,z,p-z p , z , p − z , followed by a union bound over rejected birth points, shows that their correlations remain nonpositive in every normalized block with probability at least 1 − m − 30 1-m^{-30} 1 − m − 30 . A poor rotation can increase the number of rejected candidates, but cannot remove every block containing a target: that fact follows from orthogonality alone. Thus rotations affect running time, while coverage is deterministic.
Reducing to small spheres. Within a moderate block use the finite splitting family of Wei [31 Proposition 11] . Take b = Θ ( log 2 / 3 m ) b=\Theta(\log^{2/3}m) b = Θ ( log 2/3 m ) and s = B 0 / b s=B_0/b s = B 0 / b , with dimensions rounded to powers of four. There are exp ( O ( s log B 0 ) ) = m o ( 1 ) \exp(O(s\log B_0))=m^{o(1)} exp ( O ( s log B 0 )) = m o ( 1 ) splitters. For every three vectors, one splitter preserves all squared block norms to relative error ϵ = O ( b − 1 / 2 ) \epsilon=O(b^{-1/2}) ϵ = O ( b − 1/2 ) . Admit a vector only when every block norm squared lies in [ ( 1 − ϵ ) / s , ( 1 + ϵ ) / s ] [(1-\epsilon)/s,(1+\epsilon)/s] [( 1 − ϵ ) / s , ( 1 + ϵ ) / s ] . A splitter preserving p , z , p − z p,z,p-z p , z , p − z admits both and leaves every normalized block correlation at least h − 2 ϵ h-2\epsilon h − 2 ϵ . The final splitter matrices are rational.
Checking coverage on each small sphere. Set t 0 = t / s t_0=t/\sqrt{s} t 0 = t / s . Independently in each small block, sample a finite family of rational Gaussian caps with thresholds t 0 , x t 0 t_0,xt_0 t 0 , x t 0 . Its certificate checks all pairs in a b − 2 b^{-2} b − 2 -net of the small sphere, using strengthened thresholds and a checked upper bound on every cap vector’s norm. The net has exp ( O ( b log b ) ) = m o ( 1 ) \exp(O(b\log b))=m^{o(1)} exp ( O ( b log b )) = m o ( 1 ) points. A family is accepted only after this finite test proves coverage of every pair of correlation at least h − 2 ϵ h-2\epsilon h − 2 ϵ . The certificate accepts with probability at least 1 / 2 1/2 1/2 , and its family size and verification cost are m o ( 1 ) m^{o(1)} m o ( 1 ) . A full label specifies an outer block, a splitter, and one cap from each of its s s s small blocks.
Bounding the expected label counts. A raw label is any tuple of base caps, before testing whether a point or query belongs to it. The raw number of labels in a moderate block is exp ( I h ( x ) t 2 / 2 + o ( log m ) ) = m κ I h ( x ) + o ( 1 ) \exp(I_h(x)t^2/2+o(\log m))=m^{\kappa I_h(x)+o(1)} exp ( I h ( x ) t 2 /2 + o ( log m )) = m κ I h ( x ) + o ( 1 ) . For one fixed label under the unconditioned law, concatenate its independent Gaussian vectors. The result is a standard Gaussian in the moderate block. The norm gates and positive thresholds imply a total data cap at least ( 1 − ϵ ) t (1-\epsilon)t ( 1 − ϵ ) t and a total query cap at least ( 1 − ϵ ) x t (1-\epsilon)xt ( 1 − ϵ ) x t . Therefore the data, query, and nonpositive-pair probabilities are at most
e − t 2 / 2 + o ( log m ) , e − x 2 t 2 / 2 + o ( log m ) , e − ( 1 + x 2 ) t 2 / 2 + o ( log m ) . e^{-t^2/2+o(\log m)},\qquad e^{-x^2t^2/2+o(\log m)},\qquad e^{-(1+x^2)t^2/2+o(\log m)}. e − t 2 /2 + o ( l o g m ) , e − x 2 t 2 /2 + o ( l o g m ) , e − ( 1 + x 2 ) t 2 /2 + o ( l o g m ) .
Conditioning the s s s independent base families on their certificates inflates these bounds by at most 2 s = m o ( 1 ) 2^s=m^{o(1)} 2 s = m o ( 1 ) . Multiplication by the raw-label count gives exponents κ u \kappa u κ u , κ q \kappa q κ q , and κ ( q − 1 ) \kappa(q-1) κ ( q − 1 ) , respectively. The last expression is summed over the actual m m m birth points, yielding (6) . Splitters, outer blocks, and finite precision contribute only the stated overhead. The exceptional rotation contributes negligibly: its probability is m − 30 m^{-30} m − 30 , whereas full routing and occurrence multiplicities have a deterministic polynomial bound. No subset is involved in this estimate. Increasing the fixed cutoff bounds all subpolynomial terms by m η P m^{\eta}\mathcal{P} m η P .
Accessing one label without listing all labels. The product representation also supports counting and random access. In a chunk (an outer block and splitter), let L 1 ( p ) , … , L s ( p ) L_1(p),\ldots,L_s(p) L 1 ( p ) , … , L s ( p ) be the eligible base-cap lists. Its label count is ∏ i ∣ L i ( p ) ∣ \prod_i|L_i(p)| ∏ i ∣ L i ( p ) ∣ . Compute these counts without expanding products; locate a requested rank by subtracting chunk counts, then decode it in mixed radix and rescan the base families. The complete operation costs E = m η P E=m^{\eta}\mathcal{P} E = m η P time and workspace. No point-specific base lists need be stored. For full-family sizes M a , i M_{a,i} M a , i , a raw label in chunk a a a has the injective code
1 + offset ( a ) + ∑ i ( j i − 1 ) ∏ r > i M a , r . 1+\operatorname{offset}(a)+\sum_i(j_i-1)\prod_{r>i}M_{a,r}. 1 + offset ( a ) + i ∑ ( j i − 1 ) r > i ∏ M a , r .
Offsets are sums of full products. Notice the distinction between the eligible-list radices used for a point’s rank and the full-family radices used for a label’s code.
One function for all point–label incidences
The preceding proposition proves coverage, but explicitly storing all point–label memberships may use too much space. We represent those memberships by a function that can be evaluated on demand. To answer a query label, we then recover its entire preimage. There are two requirements: every point must retain enough labels for coverage, and its retained count must satisfy a deterministic bound. We meet both by assigning each point to one of several independent certified families.
A bounded number of labels per point. An expected count alone permits an unusually long point list. Construct L f = ⌈ log 2 ( 4 m ) ⌉ L_f=\lceil\log_2(4m)\rceil L f = ⌈ log 2 ( 4 m )⌉ independent complete certified families, tagging labels by their family. Choose a computable bound B m = m κ u + η P B_m=m^{\kappa u+\eta\mathcal{P}} B m = m κ u + η P on one point’s expected count, with P ≥ 1 \mathcal{P}\ge1 P ≥ 1 ; in particular, choose B m ≥ m κ u B_m\ge m^{\kappa u} B m ≥ m κ u . Let U U U be the tagged raw universe size. Set
R = max { ⌈ 2 B m ⌉ , ⌈ U / m ⌉ , 1 } . R=\max\{\lceil2B_m\rceil,\lceil U/m\rceil,1\}. R = max {⌈ 2 B m ⌉ , ⌈ U / m ⌉ , 1 } .
Assign each point to its first family with at most R R R labels; if some point has no such family, resample the whole group. Markov’s inequality and independence bound a point’s failure by 2 − L f 2^{-L_f} 2 − L f , so group acceptance has probability at least 3 / 4 3/4 3/4 . Store only its chosen family, exact count, and generation-membership bit. Each point retains every label of its chosen family, so coverage is deterministic. Queries use all families. Assignment only removes incidences, and conditioning on group acceptance costs one factor at most 4/3 for the entire group.
Write a = κ u a=\kappa u a = κ u , b ∗ = κ q b_*=\kappa q b ∗ = κ q , and f ∗ = 1 + κ ( q − 1 ) f_*=1+\kappa(q-1) f ∗ = 1 + κ ( q − 1 ) . The construction gives m a ≤ R ≤ m a + η P m^a \le R \le m^{a+\eta}P m a ≤ R ≤ m a + η P , because κ ( 1 + u ) − 1 ≤ κ u \kappa(1+u)-1 \le\kappa u κ ( 1 + u ) − 1 ≤ κ u . All metadata and expected assignment work fit m P mP m P and m 1 + η P m^{1+\eta}P m 1 + η P , respectively. In particular, neither assignment nor a later inverse construction materializes the point–label incidence relation.
The occurrence function. An occurrence records a point together with the rank of one of its labels. The rank belongs in the domain of the function: otherwise a query could need a separate inversion for each rank. Put M = m R + 1 M=mR+1 M = m R + 1 and introduce virtual identities ι ( p , k ) = ( p − 1 ) R + k \iota(p,k)=(p-1)R+k ι ( p , k ) = ( p − 1 ) R + k , for p ∈ [ m ] p\in[m] p ∈ [ m ] , k ∈ [ R ] k\in[R] k ∈ [ R ] . They are integer addresses, not an allocated array. If λ k ( p ) \lambda_k(p) λ k ( p ) is the k k k th retained label, define
F ( ι ( p , k ) ) = { Code ( λ k ( p ) ) , p is a current member and rank k exists , ⊥ , otherwise . (7) F(\iota(p,k)) =
\begin{cases}
\operatorname{Code}(\lambda_k(p)), & p\text{ is a current member and rank }k\text{ exists},\\
\perp, & \text{otherwise}.
\end{cases} \tag*{(7)} F ( ι ( p , k )) = { Code ( λ k ( p )) , ⊥ , p is a current member and rank k exists , otherwise . (7)
The dummy identity also maps to ⊥ \perp ⊥ . For example, if R = 2 R=2 R = 2 and two points have label lists ( a , c ) (a,c) ( a , c ) and ( b , c ) (b,c) ( b , c ) , then F − 1 ( c ) = { ι ( 1 , 2 ) , ι ( 2 , 2 ) } F^{-1}(c)=\{\iota(1,2),\iota(2,2)\} F − 1 ( c ) = { ι ( 1 , 2 ) , ι ( 2 , 2 )} . One inverse query recovers both occurrences, without storing the two lists explicitly. Since U ≤ m R U\le mR U ≤ m R , this is exactly a function F : [ M ] → [ M − 1 ] ∪ { ⊥ } F:[M]\to[M-1]\cup\{\perp\} F : [ M ] → [ M − 1 ] ∪ { ⊥ } . Evaluation costs E = m η P E=m^\eta P E = m η P by the rank oracle. No fingerprint, alias, or range padding to a larger exponent is required. During a point deletion, a pending point and rank cursor additionally make its already processed ranks null; this override is part of the current-function oracle, before the point’s membership bit is cleared.
Queries and deletions. A query enumerates its raw labels and inverts each label code once. Every inverse output is an exact current point–label incidence; test the original geometric predicate and stop at its first success. An exhausted search is correct because every target shares a retained label. Repeated reports of one point are counted as occurrences. Membership is local to the frozen generation: removing a point from an unmatched set can leave it globally active. A later restoration creates a fresh insertion lifetime and never revives a deleted value of this function.
Certified inversion with a density bound
The occurrence function can be much larger than the space available for the index. Function inversion permits a smaller representation: with parameter τ \tau τ , we retain roughly M / τ M/\tau M / τ words and spend roughly τ \tau τ forward evaluations to recover a small inverse fiber. The main issue under deletions is that a once-large fiber can become sparse. We first certify complete recovery during a phase, then show how to charge recovery costs to surviving rejected occurrences.
Here a fiber is the preimage of one nonnull function value, and a value deletion changes one domain address to ⊥ \perp ⊥ . A phase freezes the function at its start and records subsequent value deletions. We use the bounded-fiber Las Vegas inverse of Bibbens, Borevitz, and McCauley [8 Theorem 5 and Section 4.3.2] , together with the phase organization of Kuszmaul and Kuszmaul [KZ26, Section 6]. The precise interface matters: the null fiber is unrestricted, recovery returns the complete preimage, and constructor workspace can be limited by batching. In particular, Theorem 5 of [8 ] imposes its fiber-size condition only on nonnull outputs of a function [ M ] → [ M − 1 ] ∪ { ⊥ } [M]\to[M-1]\cup\{\perp\} [ M ] → [ M − 1 ] ∪ { ⊥ } ; absent ranks require no sanitization.
Lemma 6.5 (Verified inverse phases). Let F : [ M ] → [ O ( M ) ] ∪ { ⊥ } F : [M] \to[O(M)] \cup\{\bot\} F : [ M ] → [ O ( M )] ∪ { ⊥ } have evaluation time E E E . For 1 ≤ τ ≤ M 1 / 3 1 \le\tau\le M^{1/3} 1 ≤ τ ≤ M 1/3 , a phase allowing O ( M / τ ) O(M/\tau) O ( M / τ ) value deletions has all-time space O ~ ( M / τ ) \widetilde{O}(M/\tau) O ( M / τ ) , expected certified construction time O ~ ( M τ 3 E ) \widetilde{O}(M\tau^3E) O ( M τ 3 E ) , and worst-case deletion work O ~ ( τ 3 E ) \widetilde{O}(\tau^3E) O ( τ 3 E ) excluding reconstruction. Every accepted phase reports exact current preimages with worst-case initialization, next-item, and termination delay O ~ ( τ 3 E ) \widetilde{O}(\tau^3E) O ( τ 3 E ) . Sequential phases have expected amortized deletion time O ~ ( τ 4 E ) \widetilde{O}(\tau^4E) O ( τ 4 E ) .
Proof. The proof separates large fibers, certifies the resulting bounded fibers, and records deletions without modifying the certified snapshot.
Splitting large fibers within the space budget. Freeze the phase-birth function F 0 F_0 F 0 . For a heavy nonnull fiber of size k > τ k > \tau k > τ , choose the least power of two at least 2 k / τ 2k/\tau 2 k / τ split buckets. A fresh logarithmic-wise independent hash has expected bucket size in ( τ / 4 , τ / 2 ] (\tau/4,\tau/2] ( τ /4 , τ /2 ] . Count all buckets and retry until every heavy bucket has size in [ τ / 16 , τ ] [\tau/16,\tau] [ τ /16 , τ ] . Bounded-independence Chernoff bounds give constant acceptance probability for τ ≥ C log 2 ( 2 M ) \tau\ge C\log^2(2M) τ ≥ C log 2 ( 2 M ) ; below this cutoff explicit lists fit the claimed space. There are O ( M / τ ) O(M/\tau) O ( M / τ ) heavy buckets. Light outputs keep their names; heavy outputs use split names. Constant-factor domain padding gives a derived function with all nonnull fibers at most τ \tau τ and an unrestricted null fiber. To identify heavy outputs without a dense count table, process the O ( M ) O(M) O ( M ) possible names in batches of Θ ( M / τ ) \Theta(M/\tau) Θ ( M / τ ) , scanning the virtual domain for each batch and retaining only heavy names and their exact counts. This costs O ~ ( M τ E ) \widetilde{O}(M\tau E) O ( M τ E ) time and O ~ ( M / τ ) \widetilde{O}(M/\tau) O ( M / τ ) workspace. A further scan counts the O ( M / τ ) O(M/\tau) O ( M / τ ) allocated heavy buckets.
Certifying the immutable inverse. The static primitive stores O ~ ( M / τ ) \widetilde{O}(M/\tau) O ( M / τ ) words and recovers a whole derived fiber in O ~ ( τ 3 E ) \widetilde{O}(\tau^3E) O ( τ 3 E ) time. Its low-workspace constructor takes expected O ~ ( M τ E ) \widetilde{O}(M\tau E) O ( M τ E ) time. Its repair dictionary contains precisely unrecovered identities; cap its size at a sufficiently large constant times M / τ M/\tau M / τ and retry if necessary. The expected repair count is O ( M / τ ) O(M/\tau) O ( M / τ ) , so this preserves constant acceptance.
We additionally certify every possible derived output, including empty outputs. Process output names in batches of size M / τ M/\tau M / τ . Scan the virtual domain to obtain exact counts for a batch; run each output’s recovery under its O ~ ( τ 3 E ) \widetilde{O}(\tau^3E) O ( τ 3 E ) cap; check all returned identities by evaluating the oracle, check distinctness in an O ( τ ) O(\tau) O ( τ ) temporary set, and compare the count. These conditions certify equality with the complete fiber. The scans cost O ~ ( M τ E ) \widetilde{O}(M\tau E) O ( M τ E ) and all recovery checks cost O ~ ( M τ 3 E ) \widetilde{O}(M\tau^3E) O ( M τ 3 E ) . Workspace is O ~ ( M / τ + τ ) = O ~ ( M / τ ) \widetilde{O}(M/\tau+\tau)=\widetilde{O}(M/\tau) O ( M / τ + τ ) = O ( M / τ ) , with no forward array of length M M M . Accepted recoveries are deterministic thereafter. All attempts obey the same space cap. Appendix § 12 also gives a direct implementation that compares actual raw-chain recoveries with exact batched fibers and stores precisely their missing identities.
Answering after deletions. During a phase, keep the old value of each deleted virtual identity in a dictionary A A A ; consult A A A before the current oracle to reconstruct F 0 F_0 F 0 exactly. Its size is O ( M / τ ) O(M/\tau) O ( M / τ ) . For a heavy output, maintain a list of split buckets having current survivors. A deletion can recover its one affected bucket to update this list in O ~ ( τ 3 E ) \widetilde{O}(\tau^3E) O ( τ 3 E ) work. An iterator recovers one nonempty bucket at a time, discards identities in A A A , and buffers at most τ \tau τ survivors. Every heavy-bucket recovery yields an output; a light output, possibly empty, needs only one bounded recovery. This gives the claimed prefix delay. Rebuild after Θ ( M / τ ) \Theta(M/\tau) Θ ( M / τ ) deletions; its conditional expected cost charges O ~ ( τ 4 E ) \widetilde{O}(\tau^4E) O ( τ 4 E ) per deletion. All statements survive exposed-seed adaptive deletions. □
A complete inverse fiber may contain many points rejected by the geometric acceptance test. Charging τ 3 \tau^3 τ 3 to every reported point would lose the space improvement. The next bound charges that cost once to a group of Ω ( τ ) \Omega(\tau) Ω ( τ ) current points. When a group becomes smaller, we store its survivors explicitly and charge their space to the deletions that made it small.
Corollary 6.6 (Density-sensitive predicate search). For Q Q Q queried nonnull names, let F F F count current-preimage occurrences rejected before the search stops. The phase finds an accepted identity or correctly reports none in
O ~ ( ( ( Q + 1 ) τ 3 + F τ 2 ) E ) , \widetilde{O}\left(((Q+1)\tau^3+F\tau^2)E\right), O ( (( Q + 1 ) τ 3 + F τ 2 ) E ) , where F F F counts rejected current-preimage occurrences. This bound is deterministic for every accepted phase and every deletion history.
Proof. Call a heavy bucket thick while it has at least τ / 32 \tau/32 τ /32 current members, and thin afterward. Maintain its exact current size. When it first drops below τ / 32 \tau/32 τ /32 , recover its survivors and store them explicitly. It had at least τ / 16 \tau/16 τ /16 birth identities, so the fewer than τ / 32 \tau/32 τ /32 new records can be charged to distinct preceding deletions in that bucket. Buckets are disjoint and become thin once per phase; all thin lists and deletion pointers therefore use O ( M / τ ) O(M/\tau) O ( M / τ ) space. The transition costs one recovery, within the deletion bound.
For a query, a completely rejected thick bucket contains Ω ( τ ) \Omega(\tau) Ω ( τ ) current rejected identities, paying for its O ~ ( τ 3 E ) \widetilde{O}(\tau^3 E) O ( τ 3 E ) recovery at cost O ~ ( τ 2 E ) \widetilde{O}(\tau^2 E) O ( τ 2 E ) per occurrence. Thin lists are explicit. Charge light-fiber setup once per queried name. At most one final thick bucket contains an accepted identity; the additive τ 3 E \tau^3 E τ 3 E term pays for it. Deleted identities never pay this charge: thickness is defined by current survivors. □
The pool interface and its optimal parameters
We now combine the certified labels with the dynamic inverse and choose their parameters. Let a = κ u a=\kappa u a = κ u be the point-label exponent, b ∗ = κ q b_*=\kappa q b ∗ = κ q the query-label exponent, and f ∗ = 1 + κ ( q − 1 ) f_*=1+\kappa(q-1) f ∗ = 1 + κ ( q − 1 ) the rejected-occurrence exponent. To obtain space exponent 1 + σ 1+\sigma 1 + σ , the inverse must save a factor of about m ( a − σ ) + m^{(a-\sigma)_+} m ( a − σ ) + from the occurrence domain. Use
v = ( a − σ ) + , τ = ⌈ m v + 2 η ⌉ , 3 v + 6 η < 1 + a . v=(a-\sigma)_+,\qquad\tau=\lceil m^{v+2\eta}\rceil,\qquad3v+6\eta<1+a. v = ( a − σ ) + , τ = ⌈ m v + 2 η ⌉ , 3 v + 6 η < 1 + a .
The extra 2 η 2\eta 2 η in τ \tau τ pays for the description and rank-oracle overhead without increasing the requested space exponent. There is no dimension factor in τ \tau τ . The final inequality ensures τ ≤ M 1 / 3 \tau\le M^{1/3} τ ≤ M 1/3 above a fixed cutoff, as required by the inverse. The following proposition records all costs needed by the dynamic construction, including construction work and deletions.
Proposition 6.7 (Implicit birth-pool interface). The resulting generation is always correct and uses at most m 1 + σ P m^{1+\sigma}\mathcal{P} m 1 + σ P space. Its expected construction work is m 1 + a + 3 v + 8 η P m^{1+a+3v+8\eta}\mathcal{P} m 1 + a + 3 v + 8 η P , and its expected amortized deletion work is m a + 4 v + 10 η P m^{a+4v+10\eta}\mathcal{P} m a + 4 v + 10 η P per original point. For each fixed rounded query z z z , a random variable Z z Z_z Z z , determined at generation construction, bounds every later query with that direction, for all surviving subsets, compatible acceptance tests, and accepted inverse phases, and
E Z z ≤ m max { b ∗ + 3 v , f ∗ + 2 v } + 8 η P . \mathbb{E}Z_z\le m^{\max\{b_*+3v,\ f_*+2v\}+8\eta}\mathcal{P}. E Z z ≤ m m a x { b ∗ + 3 v , f ∗ + 2 v } + 8 η P .
The bounds include all rejected construction attempts and low-workspace certification. Independent copies use independent complete constructions, including outer rotations and point assignments.
Proof. The domain has m 1 + a ≤ M ≤ m 1 + a + η P m^{1+a}\le M\le m^{1+a+\eta}\mathcal{P} m 1 + a ≤ M ≤ m 1 + a + η P addresses and the forward oracle costs E = m η P E=m^\eta\mathcal{P} E = m η P . Hence M / τ ≤ m 1 + a − v − η P ≤ m 1 + σ P M/\tau\le m^{1+a-v-\eta}\mathcal{P}\le m^{1+\sigma}\mathcal{P} M / τ ≤ m 1 + a − v − η P ≤ m 1 + σ P . Family descriptions, point records, and temporary rank Algorithm 3 A certified generation on an implicit occurrence domain
Build (P 0 , h , δ , x , κ , σ , η P_0,h,\delta,x,\kappa,\sigma,\eta P 0 , h , δ , x , κ , σ , η ):
Construct L f L_f L f independent certified families; compute U U U and R R R by full-product counts.
Assign every point to its first family of count at most R R R ; retry the group if an assignment fails.
Store only point records, assignments, counts, and generation-membership bits.
Define the rank oracle F F F in (7) ; build its verified inverse with parameter τ \tau τ .
Delete (p p p ):
Set the pending point to p p p and its rank cursor to 0.
for each retained rank k k k of p p p do
Save its old value and preserve it in existing snapshot logs.
Advance the pending-rank cursor to k k k , making this virtual value null.
Notify the inverse of this value deletion.
end for
Mark p p p inactive in this generation and clear the cursor.
Query (z , A z,A z , A ):
Enumerate full query labels in all families; search their exact inverse fibers using the thick/thin rule.
Return the first current identity satisfying the original predicate A A A , or NONE after exhaustion.
work fit as well. Construction costs O ~ ( M τ 3 E ) \widetilde{O}(M\tau^3E) O ( M τ 3 E ) ; deleting a point changes at most R R R values, at cost O ~ ( R τ 4 E ) \widetilde{O}(R\tau^4E) O ( R τ 4 E ) including reconstruction.
To obtain a bound that remains valid after adaptive deletions, fix z z z and count against the entire birth set. Let Q z Q_z Q z count full query routing work and labels, and let J z J_z J z count shared labels with all birth points satisfying ⟨ p , z ⟩ ≤ − δ \langle p,z\rangle\le-\delta ⟨ p , z ⟩ ≤ − δ . Thus J z J_z J z is defined before any later subset or acceptance predicate is chosen. Their expectations are at most m b ∗ + η P m^{b_*+\eta}\mathcal{P} m b ∗ + η P and m f ∗ + η P m^{f_*+\eta}\mathcal{P} m f ∗ + η P . Set Z z = O ~ ( ( ( Q z + 1 ) τ 3 + J z τ 2 ) E ) Z_z=\widetilde{O}(((Q_z+1)\tau^3+J_z\tau^2)E) Z z = O ((( Q z + 1 ) τ 3 + J z τ 2 ) E ) . The actual rejected current occurrences are a subset of these birth occurrences. The density lemma bounds work for every accepted phase by this same Z z Z_z Z z , regardless of later phase seeds. Taking expectations proves the claim. This is stronger than a bound for one subset fixed before the random choices.
Queries do not interleave with a point deletion. The cursor makes a reconstruction triggered inside that operation see the correct intermediate function; existing snapshot logs preserve their immutable functions. For background construction and replay, the exact order is formalized in Section C.1.
Choosing the density. The query bound is the larger of b ∗ + 3 v b_*+3v b ∗ + 3 v and f ∗ + 2 v f_*+2v f ∗ + 2 v . The first term pays for query labels; the second pays for rejected occurrences. Choose the density so that these exponents agree. For u ≥ σ u\ge\sigma u ≥ σ , set
κ = 1 + σ 1 + u , a = u ( 1 + σ ) 1 + u , v = u − σ 1 + u . \kappa=\frac{1+\sigma}{1+u},\qquad a=\frac{u(1+\sigma)}{1+u},\qquad v=\frac{u-\sigma}{1+u}. κ = 1 + u 1 + σ , a = 1 + u u ( 1 + σ ) , v = 1 + u u − σ .
Then the two query exponents are equal:
b ∗ + 3 v = f ∗ + 2 v = ( 1 + σ ) q h ( u ) + 3 u 1 + u − 3 σ (8) b_*+3v=f_*+2v=(1+\sigma)\frac{q_h(u)+3u}{1+u}-3\sigma \tag*{(8)} b ∗ + 3 v = f ∗ + 2 v = ( 1 + σ ) 1 + u q h ( u ) + 3 u − 3 σ (8)
The raw universe now has exponent κ ( 1 + u ) = 1 + σ \kappa(1+u)=1+\sigma κ ( 1 + u ) = 1 + σ ; the occurrence domain still contains every exact label code.
Optimizing the remaining parameter. After balancing the two query costs, only u u u remains. The following calculation gives the improved branch of the tradeoff and explains why it meets the explicit-filter curve tangentially.
Lemma 6.8 (Optimal density parameters). Let
χ h = 2 − 1 + 3 h 2 , u h = h 2 ( 1 − h 2 ) ( 1 + h 2 + 1 + 3 h 2 ) 2 . \chi_h = 2 - \sqrt{1 + 3h^2}, \qquad u_h = \frac{h^2(1-h^2)}{(1+h^2+\sqrt{1+3h^2})^2}. χ h = 2 − 1 + 3 h 2 , u h = ( 1 + h 2 + 1 + 3 h 2 ) 2 h 2 ( 1 − h 2 ) . For 0 ≤ σ ≤ ρ h 0 \le\sigma\le\rho_h 0 ≤ σ ≤ ρ h , the balanced objective in (8) , over σ ≤ u ≤ ρ h \sigma\le u \le\rho_h σ ≤ u ≤ ρ h , is minimized at u = max { σ , u h } u = \max\{\sigma,u_h\} u = max { σ , u h } . Its value is
Λ h ( σ ) = { χ h − ( 3 − χ h ) σ , 0 ≤ σ ≤ u h , q h ( σ ) , u h ≤ σ ≤ ρ h . \Lambda_h(\sigma) =
\begin{cases}
\chi_h - (3-\chi_h)\sigma, & 0 \le\sigma\le u_h,\\
q_h(\sigma), & u_h \le\sigma\le\rho_h.
\end{cases} Λ h ( σ ) = { χ h − ( 3 − χ h ) σ , q h ( σ ) , 0 ≤ σ ≤ u h , u h ≤ σ ≤ ρ h . Proof. The quotient ( q h ( u ) + 3 u ) / ( 1 + u ) (q_h(u)+3u)/(1+u) ( q h ( u ) + 3 u ) / ( 1 + u ) is the Rayleigh quotient on ( 1 , u ) (1,\sqrt{u}) ( 1 , u ) of
( 1 − h 2 − h 1 − h 2 − h 1 − h 2 3 + h 2 ) . \begin{pmatrix}
1-h^2 & -h\sqrt{1-h^2}\\
-h\sqrt{1-h^2} & 3+h^2
\end{pmatrix}. ( 1 − h 2 − h 1 − h 2 − h 1 − h 2 3 + h 2 ) . Its trace is 4 4 4 , determinant is 3 ( 1 − h 2 ) 3(1-h^2) 3 ( 1 − h 2 ) , and its negative off-diagonal entries give a positive least eigenvector. Thus its minimum is χ h = 2 − 1 + 3 h 2 \chi_h=2-\sqrt{1+3h^2} χ h = 2 − 1 + 3 h 2 , attained at
u h = h 2 ( 1 − h 2 ) ( 1 + h 2 + 1 + 3 h 2 ) 2 , x h = 3 h 1 + 1 + 3 h 2 . u_h = \frac{h^2(1-h^2)}{(1+h^2+\sqrt{1+3h^2})^2}, \qquad x_h = \frac{3h}{1+\sqrt{1+3h^2}}. u h = ( 1 + h 2 + 1 + 3 h 2 ) 2 h 2 ( 1 − h 2 ) , x h = 1 + 1 + 3 h 2 3 h . One has h < x h < 1 h<x_h<1 h < x h < 1 and 0 < u h < ρ h 0<u_h<\rho_h 0 < u h < ρ h . To verify that this is the only minimum on the nonnegative axis, put r = u r=\sqrt{u} r = u and b = h 1 − h 2 b=h\sqrt{1-h^2} b = h 1 − h 2 . The derivative of the quotient has the sign of b r 2 + 2 ( 1 + h 2 ) r − b br^2+2(1+h^2)r-b b r 2 + 2 ( 1 + h 2 ) r − b , which is strictly increasing for r ≥ 0 r\ge0 r ≥ 0 and has one positive zero. Hence the quotient increases after u h u_h u h , and the constrained choice is u = max { σ , u h } u=\max\{\sigma,u_h\} u = max { σ , u h } . The pieces meet tangentially: differentiating the Rayleigh quotient at its minimizer gives q h ′ ( u h ) = χ h − 3 q_h'(u_h)=\chi_h-3 q h ′ ( u h ) = χ h − 3 .
The query optimization alone does not establish the update bound: construction and deletions must also be affordable. § 9 verifies that construction and deletion are no more expensive, checks the native inverse restriction, and chooses rational parameters without increasing the space exponent.
What remains to obtain a fully dynamic structure. The present section constructs a deletion-only generation with a fixed birth set. New points cannot simply be inserted into an already exposed random filter family. The next section organizes separate generations for insertions and replaces the geometric centers before their certificates expire. For fixed c , σ c,\sigma c , σ and any fixed exponent allowance ω > 0 \omega>0 ω > 0 , the preceding interface has A ( n ) = n Λ c ( σ ) + ω P A(n)=n^{\Lambda_c(\sigma)+\omega}\mathcal{P} A ( n ) = n Λ c ( σ ) + ω P . Its Z z Z_z Z z variables are exactly the birth envelopes required by Lemma C.3 . That lemma gives the zero-error adaptive theorem; the capped phase schedule in Section C.1 gives its worst-case Monte Carlo counterpart. No future inverse-phase event is conditioned into the birth moment calculation. Appendix § 14 specifies a single parameter schedule giving A ( n ) = n Λ c ( σ ) + O c , σ ( ( log n ) − 1 / 100 ) P A(n)=n^{\Lambda_c(\sigma)+O_{c,\sigma}((\log n)^{-1/100})}\mathcal{P} A ( n ) = n Λ c ( σ ) + O c , σ (( l o g n ) − 1/100 ) P with a fixed polynomial degree in dimension and input length. Thus the exponent allowance can be made o ( 1 ) o(1) o ( 1 ) without hiding a dimension-dependent power in the implementation.
From birth-pool search to fully dynamic diameter
The geometric and search arguments have different requirements under updates. A center remains valid for a bounded number of changes to its input, whereas a random search index is valid only for points fixed before its random choices. We therefore use two clocks. Insertion lifetimes determine when to construct a fresh search index inside a fixed-center node. Changes to the node’s input determine when to replace its center and residual chain.
This section combines these two schedules. We first convert the search interface from deletion-only to fully dynamic membership. We then explain how replacement chains are built before their old centers expire. Finally, we combine the schedules with the local matching invariant and account for all failure events. Detailed replacement and inverse-replay schedules appear in Appendix § 13 .
The birth-pool interface. Write A ( n ) = n θ P A(n)=n^{\theta}\mathcal{P} A ( n ) = n θ P for the target time bound, where P \mathcal{P} P denotes a polynomial factor in dimension, input precision, and the relevant logarithmic parameters. Its value may increase between bounds. An index built on m m m points uses m 1 + σ P m^{1+\sigma}\mathcal{P} m 1 + σ P space, takes at most m A ( n ) P mA(n)\mathcal{P} m A ( n ) P construction work, and supports a deletion or query in A ( n ) P A(n)\mathcal{P} A ( n ) P work, with θ ≥ σ \theta\ge\sigma θ ≥ σ . For the Monte Carlo version, these are deterministic caps, and one success event guarantees correctness for all later subsets and all query directions. The certified version is always correct and supplies the conditional construction bounds and query-work variables of Proposition 6.7 ; its expected adaptive work is handled separately below.
Frozen insertion intervals
Each insertion into an unmatched search set starts a new lifetime, even when the point was previously present and has just become unmatched again. Group completed lifetimes into aligned intervals of lengths 1 1 1 , 2 2 2 , 4 4 4 , 8 8 8 , … \ldots … . Once an interval is complete, no future insertion belongs to it. Its surviving points therefore form a valid birth pool for a fresh deletion-only index. For example, the pool for lifetimes 1 , … , 4 1,\ldots,4 1 , … , 4 is fixed after insertion 4; lifetime 5 belongs to a different pool, while deletion of lifetime 3 may be applied to the old index.
Lemma 7.1 (From frozen pools to dynamic search). The birth-pool interface gives a fully dynamic search index with the same time and space exponents, up to logarithmic factors. Capped primitives and scheduled construction give worst-case bounds. For certified primitives, the expected-amortized guarantee follows from Lemma C.3 .
Proof. We retain small available indices while constructing larger ones. The proof specifies their birth sets, shows that few indices coexist, and checks correctness and space.
Birth snapshots. Keep active lifetime numbers in a persistent balanced tree. When an aligned interval of w = 2 k w=2^k w = 2 k consecutive lifetime numbers is completed, retain its active snapshot and start a construction job. Its size is m ≤ min { w , n } m\le\min\{w,n\} m ≤ min { w , n } . Draw the job’s fresh random choices only after fixing this snapshot. Later insertions lie outside the interval, so the snapshot can only lose members.
Construction and arriving deletions. Give each job O ( A ( n ) P ) O(A(n)\mathcal{P}) O ( A ( n ) P ) work per primitive operation. Its total construction and replay work is at most O ( m A ( n ) P ) O(mA(n)\mathcal{P}) O ( m A ( n ) P ) , so a sufficiently large constant budget completes it within w w w operations. For explicit lists, scan birth records in the background. Index a record only if it is still active; a deletion removes an already indexed record immediately. Per-job flags distinguish these cases. This builds the raw birth-pool index, without recursively invoking the present wrapper. Singleton intervals can be served immediately.
For an implicit index, construction uses the immutable birth function. Queue arriving deletions and replay them before activating the result. Each birth identity is deleted at most once, so the initial build and all replay work satisfy the same total budget. Section C.1 specifies the snapshot oracle and the order in which a point’s virtual ranks are deleted. In particular, advancing the rank cursor before notifying the inverse ensures that a reconstruction sees the correct intermediate function.
Available indices. Serve queries from available intervals that partition the insertion prefix. When a completed interval becomes available, replace its serving descendants unless a serving ancestor already covers it. Cancel pending descendants only at this replacement. At each length w w w , at most one job is pending: such jobs arrive every w w w insertions and finish within w w w primitive operations.
There are also at most three serving intervals of any given length. Indeed, let h h h be the current insertion count and let a serving interval of length w w w end at r r r . Its parent completes by insertion r + w r+w r + w and finishes construction within 2 w 2w 2 w further operations. If h ≥ r + 3 w h \ge r+3w h ≥ r + 3 w , that parent, or an available ancestor, must already have replaced the interval. Thus every serving interval of length w w w ends in ( h − 3 w , h ] (h-3w,h] ( h − 3 w , h ] . Since aligned endpoints are spaced w w w apart, there are at most three. Both the serving and pending collections consequently have logarithmic size.
Updates and search correctness. A predecessor search among serving intervals locates the index responsible for a deleted lifetime. Notify that index and every pending job whose snapshot contains the lifetime. Service existing jobs, activate completed intervals from largest to smallest, and then start jobs triggered by the new insertion. A query checks all serving indices. Every current point belongs to exactly one of them, so a current target is present in one queried pool. That pool’s success event remains valid because it quantifies over every later subset and direction, including choices made after its random choices are exposed.
Space and lifetime counters. At one interval length, only constantly many snapshots coexist, and each has at most n n n birth points. Hence their retained cardinalities sum to O ( n ) O(n) O ( n ) . The inequality m 1 + σ ≤ n σ m m^{1+\sigma} \le n^\sigma m m 1 + σ ≤ n σ m gives space n 1 + σ P n^{1+\sigma}P n 1 + σ P per level, including construction workspace. In one center lifetime there are at most n P nP n P primitive operations, so the number of interval levels is logarithmic in this quantity, rather than in the total age of the stream. Restart the local lifetime counter when its center is replaced. Reusable handles are reclaimed only after all retained snapshots release them. The incremental reclamation described in Appendix § 13 includes retired records in the space bound and avoids a large deallocation during one update.
Replacing the geometric chain
The preceding wrapper supports arbitrary membership changes while a node’s center remains fixed. A second schedule replaces the center before too many witnesses are deleted. A node born with m m m points is valid for Θ ( α m ) \Theta(\alpha m) Θ ( α m ) input changes. We start a replacement sufficiently early, continue serving from the old node, and spread the replacement work across the remaining changes.
A replacement consists of a whole residual chain. Constructing that chain from top to bottom immediately would be unsafe: a small residual has a short deletion tolerance and could become invalid before the larger job is ready. The schedule therefore opens each small residual late, when the common activation deadline is near. Its construction then finishes while the old chain is still valid. More precisely, a residual of current size m m m is opened only when at most α m / 4096 \alpha m/4096 α m /4096 root-pool ticks remain; a sufficiently large work budget finishes the level in O ( α 2 m ) O(\alpha^{2}m) O ( α 2 m ) ticks. The verified core removes an Ω ( α ) \Omega(\alpha) Ω ( α ) fraction of the input, leaving enough time to open its smaller child later. Lemma C.2 proves these deadline and age claims. Only serving nodes start replacement jobs: a pending chain does not recursively create more center-replacement jobs. When a chain is activated, its nodes retain their actual birth ages. The two scans in Section C.2 distinguish the immutable birth records from the current input, so insertions and deletions arriving during construction are included exactly once. The resulting number of serving and pending nodes, and all their work budgets, are polynomial in α − 1 \alpha^{-1} α − 1 , d d d , and the stated logarithmic parameters.
Completing the guarantees
Approximation and update work. Use Lemma 7.1 for each unmatched-set index in a local matching. A point update causes only constantly many matching repairs per configuration. The number of configurations and geometric levels is polynomial in d d d and the logarithmic parameters, so multiplying the schedules by these factors preserves the claimed power of n n n . Lemma 5.5 approximates every core–input distance. Assigning a diametral pair to its first core proves the global guarantee; no approximation factor is multiplied along the chain.
For explicit filters, use their uniform capped success event. For implicit filters, the certified inverse phases and their queued deletion replay give the worst-case Monte Carlo implementation in Section C.1. For zero error, use certified center blocks and synchronous suffix rebuilding. Lemma C.3 bounds expected total work despite exposed random choices: it amplifies over the whole query-direction cover and charges rare exact scans to the finite lifetime of the generation. Its accounting holds for every fixed finite prefix and needs no prescribed execution horizon.
One failure budget for the whole execution. For a horizon t t t , put S = n + t + d + B + ⌈ log ( 2 / δ ) ⌉ + 2 S = n + t + d + B + \lceil\log(2/\delta)\rceil+ 2 S = n + t + d + B + ⌈ log ( 2/ δ )⌉ + 2 , omitting B B B in the arithmetic model. The capped schedules give a predetermined polynomial bound in S S S on the number of center constructions, filter constructions, verification attempts, and witness samples. Assign conditional failure probability δ / S C 1 \delta/S^{C_1} δ / S C 1 to each relevant event, for a sufficiently large fixed C 1 C_1 C 1 . Running O ( log ( S / δ ) ) O(\log(S/\delta)) O ( log ( S / δ )) independent capped attempts gives this bound when a constructor has constant success probability. At each birth, condition on the entire previous history before drawing fresh random choices. A conditional union bound then gives probability at least 1 − δ 1-\delta 1 − δ that all required events succeed.
The work and space budgets also hold on failure outcomes. Every reported positive answer is checked against current identities; a failed or capped negative answer still triggers only the fixed number of matching repairs. A center whose core is too small is replaced by the deterministic enclosing-ball fallback from Section C.2, preserving contraction and resource bounds even though correctness is asserted only on the good event.
Uniform rank sampling is capped as well. From a pool of size m m m , draw ⌈ log 2 m ⌉ \lceil\log_2 m\rceil ⌈ log 2 m ⌉ bits and reject out-of-range integers. After O ( log ( S / δ ) ) O(\log(S/\delta)) O ( log ( S / δ )) trials, use rank one if all trials fail and charge this outcome to the failure budget. Each trial succeeds with probability at least 1 / 2 1/2 1/2 . The zero-error version uses uncapped rejection sampling, with constant conditional expected trial count.
The exact endpoint. At c = 2 c = \sqrt{2} c = 2 omit the angular indices and local matchings entirely. Maintain each node’s radius maximum and a baseline witness, together with the exact pair at each leaf. Lemma 5.2 then gives the approximation directly. The same center-replacement schedule gives worst-case Monte Carlo updates; certified disjoint blocks and synchronous suffix rebuilding give zero error with expected amortized updates. Lemma 7.2 below supplies the explicit polynomial in Theorem 1.2 .
An explicit polynomial at the endpoint. The exact 2 \sqrt{2} 2 construction uses no angular filters. The following bound makes its dependence on dimension and logarithmic parameters explicit. We choose a deliberately generous leaf cutoff so that one simple estimate covers center computation, sampling, and all replacement work; the polynomial degrees are not optimized.
Lemma 7.2 (Explicit endpoint cost). Put D = d + 3 D=d+3 D = d + 3 and H = ⌈ log 2 ( 2 D n t / δ ) ⌉ H=\lceil\log_{2}(2Dnt/\delta)\rceil H = ⌈ log 2 ( 2 D n t / δ )⌉ . The arithmetic-RAM implementation at c = 2 c=\sqrt{2} c = 2 has worst-case update time O ( D 19 H 18 ) O(D^{19}H^{18}) O ( D 19 H 18 ) and space O ( n D 19 H 18 ) O(nD^{19}H^{18}) O ( n D 19 H 18 ) .
Proof. Use the Har-Peled–Jones center constructor in the lifted dimension d + 1 d+1 d + 1 , with depth α = 1 / ( 4 D 2 ) \alpha=1/(4D^{2}) α = 1/ ( 4 D 2 ) [20 ] . Its arithmetic cost with unit-cost uniform sampling is O ( D 7 log 3 ( 2 D ) log 3 ( 2 / φ ) ) O(D^{7}\log^{3}(2D)\log^{3}(2/\varphi)) O ( D 7 log 3 ( 2 D ) log 3 ( 2/ φ )) for failure probability φ \varphi φ . Assign each construction and witness-sampling event a failure probability δ / ( 2 D n t H ) C 0 \delta/(2DntH)^{C_{0}} δ / ( 2 D n t H ) C 0 for a sufficiently large absolute constant C 0 C_{0} C 0 . All relevant logarithms are then O ( H ) O(H) O ( H ) . Uniform sampling from a persistent membership tree uses O ( H ) O(H) O ( H ) rank-search work and a deterministic O ( H ) O(H) O ( H ) cap on rejection trials. Charging this overhead to every sampling operation gives center cost C = O ( D 7 H 8 ) C=O(D^{7}H^{8}) C = O ( D 7 H 8 ) .
A baseline uses K 0 = O ( α − 1 H ) = O ( D 2 H ) K_{0}=O(\alpha^{-1}H)=O(D^{2}H) K 0 = O ( α − 1 H ) = O ( D 2 H ) fresh samples. Its complete capped sampling and distance-computation work is also at most O ( D 7 H 8 ) O(D^{7}H^{8}) O ( D 7 H 8 ) . Choose the cutoff in (10) as L = C 1 D 7 H 8 L=C_{1}D^{7}H^{8} L = C 1 D 7 H 8 , with a sufficiently large absolute constant C 1 C_{1} C 1 . This satisfies that equation, including L ≥ α − 2 L\ge\alpha^{-2} L ≥ α − 2 and L ≥ H L\ge H L ≥ H . A serving or pending chain has at most D 0 = O ( α − 1 log ( 2 n ) ) = O ( D 2 H ) D_{0}=O(\alpha^{-1}\log(2n))=O(D^{2}H) D 0 = O ( α − 1 log ( 2 n )) = O ( D 2 H ) nodes. At most D 0 D_{0} D 0 serving nodes own replacement jobs, and every such job has at most D 0 D_{0} D 0 pending levels. Hence O ( D 0 2 ) O(D_{0}^{2}) O ( D 0 2 ) node contributions suffice to account for one external update.
Each exact leaf has O ( L ) O(L) O ( L ) points; recomputing all its pair distances costs O ( d L 2 ) O(dL^{2}) O ( d L 2 ) . Radius-tree updates, fresh baseline samples, and an immediate center computation fit the same bound. At the endpoint, constructing a pending level scans and classifies its points and builds radius dictionaries; it has no matching or filter indices. The late-opening schedule allocates O ( α − 2 ( d + log n ) ) O(\alpha^{-2}(d+\log n)) O ( α − 2 ( d + log n )) work per affected job tick to these scans. Since α − 2 ≤ L \alpha^{-2}\le L α − 2 ≤ L and log n ≤ L \log n\le L log n ≤ L , this is again O ( d L 2 ) O(dL^{2}) O ( d L 2 ) for d ≥ 1 d\ge1 d ≥ 1 . Activating completed jobs and reclaiming retired records are charged to the same node budgets. Thus the total update work is
O ( d D 0 2 L 2 ) = O ( D 19 H 18 ) . O(dD_{0}^{2}L^{2})=O(D^{19}H^{18}). O ( d D 0 2 L 2 ) = O ( D 19 H 18 ) .
For space, there are O ( D 0 2 ) O(D_{0}^{2}) O ( D 0 2 ) live node structures. Each retains only a constant number of population snapshots, radius dictionaries, construction scans, and center workspaces. Population records and persistent-tree paths use O ( n H ) O(nH) O ( n H ) words per such structure; center workspace is at most C ≤ L C\le L C ≤ L . Even if all pair distances of a leaf are stored, their number is at most O ( n L ) O(nL) O ( n L ) , since the leaf contains at most min { n , O ( L ) } \min\{n,O(L)\} min { n , O ( L )} points. Including coordinates, these quantities are bounded by O ( n d L 2 ) O(ndL^{2}) O ( n d L 2 ) per node. Incremental reclamation adds only a constant factor to the simultaneously live allocation budgets. The total is therefore at most O ( n d D 0 2 L 2 ) = O ( n D 19 H 18 ) O(ndD_{0}^{2}L^{2})=O(nD^{19}H^{18}) O ( n d D 0 2 L 2 ) = O ( n D 19 H 18 ) . The zero-dimensional case is immediate. □
Limits on update time and streaming space
Our upper bounds raise two different questions. Can the update time be made polylogarithmic for every approximation arbitrarily close to one? Can the maintained state use a sublinear number of bits? We first address computation: a simple encoding and a reduction that pays for initialization rule out a uniform near-exact scheme under the randomized Orthogonal Vectors Conjecture. We then address memory by an explicit INDEX reduction. The computational statements concern ordinary randomized algorithms on inputs of bounded encoding length. The memory statement counts the entire maintained state, including the input points.
Encoding inner products as an ordinary diameter
Orthogonal Vectors and Maximum Inner Product ask for a pair with one point from each of two sets. Diameter has no such restriction. The following encoding ensures that a pair between the two encoded sets attains the diameter, so no colored-diameter oracle is needed. Let D ≥ 1 D \ge1 D ≥ 1 , let A , B ⊆ { 0 , 1 } D A, B \subseteq\{0,1\}^{D} A , B ⊆ { 0 , 1 } D be nonempty, and put M = min a ∈ A , b ∈ B ⟨ a , b ⟩ M = \min_{a \in A,b \in B} \langle a,b\rangle M = min a ∈ A , b ∈ B ⟨ a , b ⟩ .
Lemma 8.1 (An uncolored diameter encoding). In O ( ( ∣ A ∣ + ∣ B ∣ ) D ) O((|A| + |B|)D) O (( ∣ A ∣ + ∣ B ∣ ) D ) time one can construct a strict set P ⊆ { 0 , 1 } 5 D P \subseteq\{0,1\}^{5D} P ⊆ { 0 , 1 } 5 D of size ∣ A ∣ + ∣ B ∣ |A| + |B| ∣ A ∣ + ∣ B ∣ with diam ( P ) 2 = 4 D − 2 M \operatorname{diam}(P)^2 = 4D - 2M diam ( P ) 2 = 4 D − 2 M . A factor-( 1 + ε ) (1+\varepsilon) ( 1 + ε ) diameter estimate therefore gives an estimate of M M M in [ M , M + 4 ε D ] [M, M + 4\varepsilon D] [ M , M + 4 ε D ] .
Proof. We encode the two sets separately, compare cross distances with within-set distances, and then translate the approximation error. Use the injective maps
F ( a ) = ( a , 1 − a , 0 D , 0 2 D ) , G ( b ) = ( b , 0 D , 1 − b , 1 2 D ) . F(a) = (a,1-a,0_D,0_{2D}), \qquad G(b) = (b,0_D,1-b,1_{2D}). F ( a ) = ( a , 1 − a , 0 D , 0 2 D ) , G ( b ) = ( b , 0 D , 1 − b , 1 2 D ) .
The final 2 D 2D 2 D coordinates make their images disjoint. For a cross pair, coordinatewise expansion gives
∥ F ( a ) − G ( b ) ∥ 2 = ∑ i = 1 D ( ( a i − b i ) 2 + ( 1 − a i ) 2 + ( 1 − b i ) 2 + 2 ) = 4 D − 2 ⟨ a , b ⟩ ≥ 2 D . \begin{aligned}
\lVert F(a)-G(b)\rVert^2
&= \sum_{i=1}^{D}((a_i-b_i)^2+(1-a_i)^2+(1-b_i)^2+2) \\
&= 4D-2\langle a,b\rangle\ge2D.
\end{aligned} ∥ F ( a ) − G ( b ) ∥ 2 = i = 1 ∑ D (( a i − b i ) 2 + ( 1 − a i ) 2 + ( 1 − b i ) 2 + 2 ) = 4 D − 2 ⟨ a , b ⟩ ≥ 2 D .
Two points in either one image have squared distance at most 2 D 2D 2 D . Thus a cross pair attains the diameter of F ( A ) ∪ G ( B ) F(A) \cup G(B) F ( A ) ∪ G ( B ) , proving the identity. For a one-coordinate illustration, the cross contribution is four unless both input bits are one, when it is two.
Now let L L L be a valid approximate diameter, so that diam ( P ) / ( 1 + ε ) ≤ L ≤ diam ( P ) \operatorname{diam}(P)/(1+\varepsilon) \le L \le\operatorname{diam}(P) diam ( P ) / ( 1 + ε ) ≤ L ≤ diam ( P ) . Define M ^ = ( 4 D − L 2 ) / 2 \widehat{M}=(4D-L^2)/2 M = ( 4 D − L 2 ) /2 . The identity just proved yields
0 ≤ M ^ − M = diam ( P ) 2 − L 2 2 ≤ 2 D ( 1 − ( 1 + ε ) − 2 ) ≤ 4 ε D . 0 \le\widehat{M}-M = \frac{\operatorname{diam}(P)^2-L^2}{2} \le2D(1-(1+\varepsilon)^{-2}) \le4\varepsilon D. 0 ≤ M − M = 2 diam ( P ) 2 − L 2 ≤ 2 D ( 1 − ( 1 + ε ) − 2 ) ≤ 4 ε D .
This proves the approximation statement.
An orthogonal cross pair exists exactly when M = 0 M=0 M = 0 . The two possible squared-diameter ranges are therefore 4 D 4D 4 D and at most 4 D − 2 4D-2 4 D − 2 . Setting ε = 1 / ( 8 D ) \varepsilon=1/(8D) ε = 1/ ( 8 D ) preserves this distinction, since 4 D / ( 1 + 1 / ( 8 D ) ) 2 > 4 D − 2 4D/(1+1/(8D))^2 > 4D-2 4 D / ( 1 + 1/ ( 8 D ) ) 2 > 4 D − 2 . For maximum inner product, first replace a a a by ( a , 1 − a ) (a,1-a) ( a , 1 − a ) and b b b by ( 1 − b , 1 ) (1-b,1) ( 1 − b , 1 ) . Their inner product becomes D − ⟨ a , b ⟩ D-\langle a,b\rangle D − ⟨ a , b ⟩ . Applying the lemma in dimension 2 D 2D 2 D then yields a diameter instance in dimension 10 D 10D 10 D and an additive 8 ε D 8\varepsilon D 8 ε D approximation to the original maximum.
Paying for initialization only once
A dynamic lower bound must include the time to initialize the data structure. In particular, inserting all points into one very large structure is not useful if that initialization already takes quadratic time. We instead choose a smaller capacity and reuse the same initialized structure for many block pairs. It is emptied by legal deletions between pairs; it is never initialized again.
For this reduction, let r r r be the size of each static input set and let m m m be the capacity of the reusable dynamic structure. Assume empty initialization takes m K + o ( 1 ) m^{K+o(1)} m K + o ( 1 ) time, an update takes m α + o ( 1 ) m^{\alpha+o(1)} m α + o ( 1 ) amortized time, and reading an answer takes m β + o ( 1 ) m^{\beta+o(1)} m β + o ( 1 ) time. Empty initialization has no access to future coordinates. Polynomial factors in logarithmic dimension, inverse-polylogarithmic accuracy, and logarithmic execution length are included in the o ( 1 ) o(1) o ( 1 ) terms. Write s = max { 1 + α , β } s=\max\{1+\alpha,\beta\} s = max { 1 + α , β } .
Lemma 8.2 (Reusing one initialized structure). If s < 2 s<2 s < 2 , the corresponding static encoded problem on two r r r -point sets can be solved in time r Ψ K ( s ) + o ( 1 ) r^{\Psi_K(s)+o(1)} r Ψ K ( s ) + o ( 1 ) , where
Ψ K ( s ) = { s , K ≤ s , 2 K / ( K + 2 − s ) , K > s . \Psi_K(s)=\begin{cases}
s, & K\le s,\\
2K/(K+2-s), & K>s.
\end{cases} Ψ K ( s ) = { s , 2 K / ( K + 2 − s ) , K ≤ s , K > s . The same implication holds for expected amortized work and bounded error on each read, with constant error in the static algorithm.
Proof. We first count operations for an arbitrary capacity m m m , then choose m m m to balance initialization with the work over all block pairs. Partition each input set into blocks of size at most ⌊ m / 2 ⌋ \lfloor m/2\rfloor ⌊ m /2 ⌋ . For every nonempty block pair ( A i , B j ) (A_i,B_j) ( A i , B j ) , insert its encoded points, read the approximate diameter, and delete all those points. For example, two blocks on each side give the four runs ( A 1 , B 1 ) , ( A 1 , B 2 ) , ( A 2 , B 1 ) , ( A 2 , B 2 ) (A_1,B_1),(A_1,B_2),(A_2,B_1),(A_2,B_2) ( A 1 , B 1 ) , ( A 1 , B 2 ) , ( A 2 , B 1 ) , ( A 2 , B 2 ) , all using the same initialized state. The update sequence is fixed before the algorithm’s random choices, and the capacity is respected in every run.
There are O ( r 2 / m 2 ) O(r^2/m^2) O ( r 2 / m 2 ) runs, using O ( r 2 / m ) O(r^2/m) O ( r 2 / m ) updates and O ( r 2 / m 2 ) O(r^2/m^2) O ( r 2 / m 2 ) reads in total. Taking the appropriate extremum of the block answers gives the answer for the full static instance. Including input reading, the total work is
r 1 + o ( 1 ) + m K + o ( 1 ) + r 2 m s − 2 + o ( 1 ) . r^{1+o(1)}+m^{K+o(1)}+r^2m^{s-2+o(1)}. r 1 + o ( 1 ) + m K + o ( 1 ) + r 2 m s − 2 + o ( 1 ) .
If K ≤ s K\le s K ≤ s , choose m = Θ ( r ) m=\Theta(r) m = Θ ( r ) . Otherwise choose m = Θ ( r 2 / ( K + 2 − s ) ) m=\Theta(r^{2/(K+2-s)}) m = Θ ( r 2/ ( K + 2 − s ) ) , which balances the last two terms. These choices give the stated exponent. Since K K K and s s s are fixed, r r r is a fixed power of m m m , and the complete sequence has length polynomial in m m m .
For bounded-error reads, use O ( log r ) O(\log r) O ( log r ) independent copies and take the median estimate for each block pair. The probability that any block estimate fails can be made at most 1 / 100 1/100 1/100 , without changing an exponent. For expected amortized work, apply the total-work bound to this one legal sequence, including all its returns to the empty set. Stopping after a sufficiently large constant multiple of the expected work adds only a constant error probability by Markov’s inequality. The resulting static algorithm has bounded error and the claimed worst-case running time. ∎
Consequences for near-exact approximation
We use the following randomized form of the Orthogonal Vectors Conjecture (OVC): for every η > 0 \eta>0 η > 0 , there is a constant C C C for which no bounded-error randomized O ( r 2 − η ) O(r^{2-\eta}) O ( r 2 − η ) -time algorithm decides whether two r r r -point sets in { 0 , 1 } C log r \{0,1\}^{C\log r} { 0 , 1 } C l o g r contain a pair with inner product zero [16 ] . Here bounded error means success probability at least 2 / 3 2/3 2/3 on every input.
The encoding uses accuracy proportional to 1 / log r 1/\log r 1/ log r . Consequently, a polynomial dependence on the inverse accuracy cannot offset a fixed saving in the update exponent. The reuse lemma makes this observation valid even when the initialization degree is large.
Corollary 8.3 (Uniform accuracy). Assume randomized OVC. Fix K ≥ 0 K\ge0 K ≥ 0 , 0 < γ < 1 0<\gamma<1 0 < γ < 1 , and a polynomial p p p . No single fully dynamic ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -diameter scheme, valid for all 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , can have
initialization time n K p ( d , ε − 1 , log ( 2 n t ) ) n^{K}p(d,\varepsilon^{-1},\log(2nt)) n K p ( d , ε − 1 , log ( 2 n t )) , expected amortized update time n 1 − γ p ( d , ε − 1 , log ( 2 n t ) ) n^{1-\gamma}p(d,\varepsilon^{-1},\log(2nt)) n 1 − γ p ( d , ε − 1 , log ( 2 n t )) , constant-time answer retrieval, and success probability at least 2 / 3 2/3 2/3 on each read. This holds already for binary strict sets, d = O ( log n ) d = O(\log n) d = O ( log n ) , ε = Θ ( 1 / log n ) \varepsilon= \Theta(1/\log n) ε = Θ ( 1/ log n ) , and a polynomial update horizon t t t .
Proof. The saving in the static running time is determined before the OVC dimension constant is chosen. Put s = 2 − γ s = 2 - \gamma s = 2 − γ . For every fixed K K K , Lemma 8.2 gives Ψ K ( s ) < 2 \Psi_K(s) < 2 Ψ K ( s ) < 2 . Choose 0 < η < 2 − Ψ K ( s ) 0 < \eta< 2 - \Psi_K(s) 0 < η < 2 − Ψ K ( s ) and take the dimension constant C C C supplied by OVC for that η \eta η .
Given the corresponding Orthogonal Vectors instance, apply Lemma 8.1 with D = ⌈ C log r ⌉ D = \lceil C \log r\rceil D = ⌈ C log r ⌉ and ε = 1 / ( 8 D ) \varepsilon= 1/(8D) ε = 1/ ( 8 D ) . The approximate diameter determines whether an orthogonal pair exists. The reuse lemma chooses a capacity m = r Θ ( 1 ) m = r^{\Theta(1)} m = r Θ ( 1 ) , so the dimension, inverse accuracy, execution horizon, and amplification factors contribute only polynomial logarithmic overhead. It gives a bounded-error algorithm in time r Ψ K ( s ) + o ( 1 ) r^{\Psi_K(s)+o(1)} r Ψ K ( s ) + o ( 1 ) , contradicting the chosen OVC instance. □
The expected-work assumption concerns every fixed legal prefix starting empty, so the corollary also applies to Las Vegas structures. Its quantifier order matters: K K K , the polynomial p p p , and the saving γ \gamma γ are fixed before ε \varepsilon ε is chosen. The statement therefore permits an update saving that tends to zero as ε \varepsilon ε tends to zero, as in our upper bounds.
A fixed accuracy after fixing the initialization degree. A second consequence uses a constant-gap reduction. For C ≥ 1 C \ge1 C ≥ 1 and 0 < η < 1 / 2 0 < \eta< 1/2 0 < η < 1/2 , let IP ( C , η ) \operatorname{IP}(C,\eta) IP ( C , η ) be the hypothesis that no bounded-error O ( r 2 − η ) O(r^{2-\eta}) O ( r 2 − η ) -time algorithm decides whether two r r r -point binary sets in dimension ⌈ C log r ⌉ \lceil C\log r\rceil ⌈ C log r ⌉ have a cross pair of a specified exact inner product. Abboud–Ron-Zewi [6 Lemma 4.1] imply that this hypothesis rules out additive Maximum Inner Product approximation with error Θ ~ ( η / C 2 ) \widetilde{\Theta}(\eta/C^2) Θ ( η / C 2 ) times the dimension in O ( r 2 − 2 η − ζ ) O(r^{2-2\eta-\zeta}) O ( r 2 − 2 η − ζ ) time, for any fixed ζ > 0 \zeta> 0 ζ > 0 . The target dimension is O C , η ( log r ) O_{C,\eta}(\log r) O C , η ( log r ) . The strict saving ζ \zeta ζ absorbs the logarithmic amplification needed for randomized algorithms.
Combining their reduction with our maximum-inner-product encoding and the reuse lemma gives a constant ε C , η > 0 \varepsilon_{C,\eta} > 0 ε C , η > 0 for which a dynamic ( 1 + ε C , η ) (1+\varepsilon_{C,\eta}) ( 1 + ε C , η ) -approximation with s < 2 s < 2 s < 2 must satisfy Ψ K ( s ) ≥ 2 − 2 η \Psi_K(s) \ge2 - 2\eta Ψ K ( s ) ≥ 2 − 2 η . For constant-time answer retrieval this is
α ≥ 1 − max { 2 η , K η 1 − η } . \alpha\ge1-\max\left\{2\eta,\frac{K\eta}{1-\eta}\right\}. α ≥ 1 − max { 2 η , 1 − η K η } .
Indeed, on the branch K ≤ s = 1 + α K \le s = 1+\alpha K ≤ s = 1 + α the inequality is s ≥ 2 − 2 η s \ge2 - 2\eta s ≥ 2 − 2 η ; on the other branch it rearranges to s ≥ 2 − K η / ( 1 − η ) s \ge2 - K\eta/(1-\eta) s ≥ 2 − K η / ( 1 − η ) .
Randomized OVC implies that for every η \eta η there is some C = C ( η ) C = C(\eta) C = C ( η ) satisfying IP ( C , η ) \operatorname{IP}(C,\eta) IP ( C , η ) , because exact inner product includes orthogonality. After fixing K K K , choose η \eta η small enough that the displayed lower bound is positive. This gives a fixed error ε K > 0 \varepsilon_K > 0 ε K > 0 for which polynomial-logarithmic updates and reads are impossible with initialization degree K K K . Thus the error depends on the initialization degree; this argument does not give a matching update lower bound for each prescribed c < 2 c < \sqrt{2} c < 2 .
Linear memory below 2 \sqrt{2} 2
For memory, a one-way communication reduction already applies to insertion-only streams. We adapt the INDEX construction of Agarwal–Sharathkumar [7 ] , using nearly orthogonal sign vectors to obtain a logarithmic dimension bound at every fixed c < 2 c < \sqrt{2} c < 2 . In INDEX, Alice receives a bit string x ∈ { 0 , 1 } m x \in\{0,1\}^{m} x ∈ { 0 , 1 } m , Bob receives an index j j j , and Alice sends one message from which Bob must recover x j x_j x j . Any randomized protocol with success probability at least 2 / 3 2/3 2/3 requires Ω ( m ) \Omega(m) Ω ( m ) bits, even with public randomness.
Proposition 8.4 (An adapted INDEX lower bound). For every fixed 1 ≤ c < 2 1 \le c < \sqrt{2} 1 ≤ c < 2 , estimating Euclidean diameter within factor c c c with probability at least 2 / 3 2/3 2/3 requires Ω c ( n ) \Omega_c(n) Ω c ( n ) bits of state, even for insertion-only strict sets of sign vectors in dimension O c ( log n ) O_c(\log n) O c ( log n ) .
Proof. Choose a fixed 0 < ξ < min { 1 , 2 / c 2 − 1 } 0 < \xi< \min\{1, 2/c^2 - 1\} 0 < ξ < min { 1 , 2/ c 2 − 1 } . There exist m m m sign vectors v 1 , … , v m ∈ { − 1 , 1 } d v_1,\ldots,v_m \in\{-1,1\}^d v 1 , … , v m ∈ { − 1 , 1 } d , where d = O ( ξ − 2 log ( m + 1 ) ) d = O(\xi^{-2}\log(m+1)) d = O ( ξ − 2 log ( m + 1 )) , such that ∣ ⟨ v i , v j ⟩ ∣ ≤ ξ d |\langle v_i,v_j\rangle| \le\xi d ∣ ⟨ v i , v j ⟩ ∣ ≤ ξ d for i ≠ j i \ne j i = j . To see existence, draw the sign vectors independently. A standard Chernoff bound gives probability at most 2 e − ξ 2 d / 2 2e^{-\xi^2d/2} 2 e − ξ 2 d /2 that one pair violates the inequality, so a union bound over all pairs is less than one for a sufficiently large constant in d d d . Fix such a family and make it known to both parties.
Alice inserts v i v_i v i exactly when x i = 1 x_i = 1 x i = 1 and sends the algorithm’s entire state to Bob. Bob continues the computation by inserting − v j -v_j − v j . The stream is a strict set: the correlation bound excludes both duplicate and antipodal vectors among distinct v i v_i v i ’s. Its capacity is at most m + 1 m+1 m + 1 .
If x j = 1 x_j = 1 x j = 1 , the final set contains v j , − v j v_j,-v_j v j , − v j , so its diameter is 2 d 2\sqrt{d} 2 d . If x j = 0 x_j = 0 x j = 0 , every pair has squared distance at most 2 ( 1 + ξ ) d 2(1+\xi)d 2 ( 1 + ξ ) d . This holds for pairs v i , v k v_i,v_k v i , v k because their squared distance is 2 d − 2 ⟨ v i , v k ⟩ 2d - 2\langle v_i,v_k\rangle 2 d − 2 ⟨ v i , v k ⟩ , and for pairs v i , − v j v_i,-v_j v i , − v j because it is 2 d + 2 ⟨ v i , v j ⟩ 2d + 2\langle v_i,v_j\rangle 2 d + 2 ⟨ v i , v j ⟩ . Since
2 d c > 2 ( 1 + ξ ) d , \frac{2\sqrt{d}}{c} > \sqrt{2(1+\xi)d}, c 2 d > 2 ( 1 + ξ ) d ,
a valid factor-c c c diameter estimate distinguishes the two cases. An s s s -bit state would therefore give an s s s -bit INDEX message. The communication lower bound yields s = Ω ( m ) s = \Omega(m) s = Ω ( m ) ; taking n = m + 1 n = m+1 n = m + 1 proves the proposition. □
With Θ ( log n ) \Theta(\log n) Θ ( log n ) -bit words, this is Ω c ( n / log n ) \Omega_c(n/\log n) Ω c ( n / log n ) words. Hence the exponent of n n n in our near-linear space bounds is best possible on these bounded-coordinate inputs, up to polynomial logarithmic factors. The bound charges all memory; it does not grant free external access to the active set. It supplies no corresponding update-time lower bound.
For general constant approximation factors, Padaki–Singal–Waingarten [28 ] obtain an Ω ~ ( 1 / c 2 ) \widetilde{\Omega}(1/c^2) Ω ( 1/ c 2 ) space lower bound in strict-turnstile streams, where frequencies remain nonnegative after every update. Their setting permits arbitrary stream length and multiplicities, bounds the final support by n n n , and uses a public-randomness budget independent of stream length. These assumptions differ from short strict-set streams. Polynomial-length sketch simulations [24 ] have their own model conditions, so they do not by themselves transfer that theorem to our bounded-multiplicity setting. The proposition above provides the memory comparison needed for our results below 2 \sqrt{2} 2 without such a transfer.
Parameter choices and final resource bounds
The previous sections establish the geometric guarantee, the search operations, and their dynamic composition. We now choose their parameters to obtain the exponents in the introduction. There are two issues to check. In the explicit construction, rounding must not increase the space exponent, and the geometric margins must cost only a constant factor in time. In the implicit construction, the cost of building and updating the inverse must stay below its query bound. We give these verifications separately.
Throughout, fix 1 < c < 2 1 < c < \sqrt{2} 1 < c < 2 and write g = c 2 − 1 g = c^2 - 1 g = c 2 − 1 , ρ = 2 / c 2 − 1 \rho= 2/c^2 - 1 ρ = 2/ c 2 − 1 , and L = ⌈ log 2 ( 2 n ) ⌉ L = \lceil\log_2(2n)\rceil L = ⌈ log 2 ( 2 n )⌉ . All constants in this section may depend on c c c , but not on the coordinates or their spread.
Explicit filters with exact exponents
Recall that e e e is the radial and angular rounding margin, γ \gamma γ is the strong-edge distance factor, κ = γ + 2 e \kappa=\gamma+2e κ = γ + 2 e pays for radial rounding, and λ \lambda λ is the ratio between distance scales. Taking e e e of order 1 / log n 1/\log n 1/ log n makes all rounding losses in the exponent of order 1 / log n 1/\log n 1/ log n , which contributes only a constant factor to the running time.
Lemma 9.1 (Geometric and filter parameter choices). For every 0 ≤ σ ≤ ρ 0 \le\sigma\le\rho 0 ≤ σ ≤ ρ , the geometric construction has O c ( L 3 ) O_c(L^3) O c ( L 3 ) configurations per node, with a common positive correlation h = g − O c ( 1 / L ) h=g-O_c(1/L) h = g − O c ( 1/ L ) . The explicit index can be chosen with point-incidence exponent u ≤ σ u \le\sigma u ≤ σ and query exponent q ≤ Q c ( σ ) + O c ( 1 / L ) q \le Q_c(\sigma)+O_c(1/L) q ≤ Q c ( σ ) + O c ( 1/ L ) .
Proof. Geometric margins. Choose rational e e e within a factor of two below min { ( c − 1 ) / 32 , 1 / ( 1024 L ) } \min\{(c-1)/32,1/(1024L)\} min {( c − 1 ) /32 , 1/ ( 1024 L )} and rational γ ∈ [ c − 4 e , c − 3 e ] \gamma\in[c-4e,c-3e] γ ∈ [ c − 4 e , c − 3 e ] . Set κ = γ + 2 e \kappa=\gamma+2e κ = γ + 2 e , λ = 1 + e / ( 4 κ ) \lambda=1+e/(4\kappa) λ = 1 + e / ( 4 κ ) , and K = ⌈ 2 / ( c − 1 ) ⌉ K=\lceil2/(c-1)\rceil K = ⌈ 2/ ( c − 1 )⌉ . Then γ > 1 \gamma>1 γ > 1 , κ λ ≤ c − 3 e / 4 < c \kappa\lambda\le c-3e/4<c κλ ≤ c − 3 e /4 < c , and 1 + 1 / K < c 1+1/K<c 1 + 1/ K < c . These are precisely the requirements of § 5 . The radial mesh and the distance scales each have O c ( L ) O_c(L) O c ( L ) choices, so there are O c ( L 3 ) O_c(L^3) O c ( L 3 ) configurations.
Use the padding margin e e e from Lemma 5.6 and set
h = γ 2 − 1 − 11 e . h=\gamma^2-1-11e. h = γ 2 − 1 − 11 e .
Since e ≤ ( c − 1 ) / 32 e\le(c-1)/32 e ≤ ( c − 1 ) /32 and γ ≥ 1 + 7 ( c − 1 ) / 8 \gamma\ge1+7(c-1)/8 γ ≥ 1 + 7 ( c − 1 ) /8 , e ≤ ( γ 2 − 1 ) / 16 e\le(\gamma^2-1)/16 e ≤ ( γ 2 − 1 ) /16 and h ≥ 45 ( c − 1 ) / 32 > 0 h\ge45(c-1)/32>0 h ≥ 45 ( c − 1 ) /32 > 0 . Also h < g h<g h < g and g − h ≤ ( 8 2 + 11 ) e = O c ( 1 / L ) g-h\le(8\sqrt{2}+11)e=O_c(1/L) g − h ≤ ( 8 2 + 11 ) e = O c ( 1/ L ) . Thus the common-gap lemma applies, including its margin for query rounding and negative correlation of rejected candidates.
Rounding the filter parameter downward. Put J = 128 L J=128L J = 128 L and σ n = ⌊ J 2 σ ⌋ / J 2 \sigma_n=\lfloor J^2\sigma\rfloor/J^2 σ n = ⌊ J 2 σ ⌋ / J 2 . The ideal parameter is x ∗ = h + σ n 1 − h 2 x_\ast=h+\sqrt{\sigma_n}\sqrt{1-h^2} x ∗ = h + σ n 1 − h 2 . Choose the largest x ∈ h + J − 1 Z ≥ 0 x\in h+J^{-1}\mathbb{Z}_{\ge0} x ∈ h + J − 1 Z ≥ 0 with x ≤ x ∗ x\le x_\ast x ≤ x ∗ . Squaring the comparison decides this choice with rational arithmetic. Since σ n ≤ ρ ≤ ( 1 − h ) / ( 1 + h ) \sigma_n\le\rho\le(1-h)/(1+h) σ n ≤ ρ ≤ ( 1 − h ) / ( 1 + h ) , we have h ≤ x ≤ 1 h\le x\le1 h ≤ x ≤ 1 . Consequently
u = ( x − h ) 2 1 − h 2 ≤ σ n ≤ σ , q = ( 1 − h x ) 2 1 − h 2 ≤ Q c ( σ ) + O c ( 1 / L ) . u=\frac{(x-h)^2}{1-h^2}\le\sigma_n\le\sigma,\qquad q=\frac{(1-hx)^2}{1-h^2}\le Q_c(\sigma)+O_c(1/L). u = 1 − h 2 ( x − h ) 2 ≤ σ n ≤ σ , q = 1 − h 2 ( 1 − h x ) 2 ≤ Q c ( σ ) + O c ( 1/ L ) .
For completeness, the second inequality follows from σ − σ n ≤ 1 / J \sqrt{\sigma}-\sqrt{\sigma_n}\le1/J σ − σ n ≤ 1/ J and x ∗ − x < 1 / J x_\ast-x<1/J x ∗ − x < 1/ J . The derivative of q q q with respect to x x x has magnitude at most 2 2 2 on [ h , 1 ] [h,1] [ h , 1 ] . The function ( 1 − s 2 − s z ) 2 (\sqrt{1-s^2}-sz)^2 ( 1 − s 2 − sz ) 2 has derivatives of magnitude at most 4 4 4 in s s s and 1 1 1 in z z z on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ; the same bounds hold at the boundary of its zero region by continuity. Applying these bounds to h = g − O c ( 1 / L ) h=g-O_c(1/L) h = g − O c ( 1/ L ) proves the estimate uniformly over 0 ≤ σ ≤ ρ 0\le\sigma\le\rho 0 ≤ σ ≤ ρ . When σ = 0 \sigma=0 σ = 0 , choose x = h x=h x = h exactly, so that u = 0 u=0 u = 0 with no rounding loss. □ \square □
Construction cost and the absence of an exponent loss. Choose fixed tensor depth ℓ ≥ 16 / ρ \ell\ge16/\rho ℓ ≥ 16/ ρ . For the explicit Gaussian construction, the probability estimates are uniform over the compact range of h h h above and h ≤ x ≤ 1 h\le x\le1 h ≤ x ≤ 1 . The exponent of each base family is at most I h ( x ) / ℓ = ( 1 + u ) / ℓ ≤ ρ / 8 I_h(x)/\ell=(1+u)/\ell\le\rho/8 I h ( x ) / ℓ = ( 1 + u ) / ℓ ≤ ρ /8 . For a birth pool of size m m m , the point work, query work, and space are therefore bounded, respectively, by
( m u + m ρ / 8 ) P , ( m q + m ρ / 8 ) P , ( m 1 + u + m ρ / 8 ) P , (m^u+m^{\rho/8})\mathcal{P},\qquad(m^q+m^{\rho/8})\mathcal{P},\qquad(m^{1+u}+m^{\rho/8})\mathcal{P}, ( m u + m ρ /8 ) P , ( m q + m ρ /8 ) P , ( m 1 + u + m ρ /8 ) P ,
where P \mathcal{P} P is polynomial in dimension and the logarithmic parameters. Since m ≤ n m\le n m ≤ n , m q ≤ m Q c ( σ ) exp ( O c ( log m / L ) ) = O c ( m Q c ( σ ) ) . m^q\le m^{Q_c(\sigma)}\exp(O_c(\log m/L))=O_c(m^{Q_c(\sigma)}). m q ≤ m Q c ( σ ) exp ( O c ( log m / L )) = O c ( m Q c ( σ ) ) . Moreover Q c ( σ ) ≥ ρ ≥ σ Q_c(\sigma)\ge\rho\ge\sigma Q c ( σ ) ≥ ρ ≥ σ , so both maintenance and construction fit the same update budget. Only nonempty full filter buckets are stored. The implicit direction net contributes O ( d log ( d / e ) ) O(d\log(d/e)) O ( d log ( d / e )) to amplification, rather than its cardinality to space, because it is never enumerated.
The dynamic composition thus gives update time n Q c ( σ ) poly c , σ ( d , log ( 2 n t / δ ) ) n^{Q_c(\sigma)}\operatorname{poly}_{c,\sigma}(d,\log(2nt/\delta)) n Q c ( σ ) poly c , σ ( d , log ( 2 n t / δ )) and space n 1 + σ poly c , σ ( d , log ( 2 n t / δ ) ) n^{1+\sigma}\operatorname{poly}_{c,\sigma}(d,\log(2nt/\delta)) n 1 + σ poly c , σ ( d , log ( 2 n t / δ )) . Putting σ = ρ \sigma=\rho σ = ρ proves Theorem 1.1 ; the same calculation proves the full explicit curve stated after that theorem.
The implicit tradeoff and maintenance costs
The implicit construction may assign more labels to a point than the final space bound allows us to store. The inverse compresses these incidences, but recovering a bucket takes additional time. The density-sensitive search bound makes it possible to balance the two kinds of recovery cost. The optimization in the search section determines the query exponent. Here we check that deletions, construction, and workspace obey the same tradeoff.
Choose a small fixed geometric margin, so h h h is close to g g g and rejected correlations remain negative. Let η > 0 \eta>0 η > 0 be the exponent allowance used by the certified finite families. For u ≥ σ u\ge\sigma u ≥ σ , define
κ = 1 + σ 1 + u , a = κ u , b = κ q h ( u ) , f = 1 + κ ( q h ( u ) − 1 ) , v = a − σ . \kappa=\frac{1+\sigma}{1+u},\qquad a=\kappa u,\qquad b=\kappa q_h(u),\qquad f=1+\kappa(q_h(u)-1),\qquad v=a-\sigma. κ = 1 + u 1 + σ , a = κ u , b = κ q h ( u ) , f = 1 + κ ( q h ( u ) − 1 ) , v = a − σ .
where
q h ( u ) = ( 1 − h 2 − h u ) 2 . q_h(u)=\left(\sqrt{1-h^2}-h\sqrt{u}\right)^2. q h ( u ) = ( 1 − h 2 − h u ) 2 .
Here a a a controls point labels, b b b controls query labels, and f f f controls rejected incidences in the whole birth pool. The inverse parameter is τ = ⌈ m v + 2 η ⌉ \tau=\lceil m^{v+2\eta}\rceil τ = ⌈ m v + 2 η ⌉ . The extra 2 η 2\eta 2 η absorbs description and route-count factors in space; it does not introduce an extra power of m m m in the final space bound.
The birth-pool interface gives the following leading exponents. Time exponents have an additional O ( η ) O(\eta) O ( η ) allowance, whereas the space exponent shown is exact.
Table 9.2.
The inverse construction additionally requires 3 v + 6 η < 1 + a 3v+6\eta<1+a 3 v + 6 η < 1 + a . We next verify that the optimizer satisfies this restriction and that maintenance never exceeds the query exponent.
Put S h = 1 + 3 h 2 S_h=\sqrt{1+3h^2} S h = 1 + 3 h 2 , χ h = 2 − S h \chi_h=2-S_h χ h = 2 − S h , and u h = h 2 ( 1 − h 2 ) / ( 1 + h 2 + S h ) 2 u_h=h^2(1-h^2)/(1+h^2+S_h)^2 u h = h 2 ( 1 − h 2 ) / ( 1 + h 2 + S h ) 2 . Use the optimizer u = max { σ , u h } u=\max\{\sigma,u_h\} u = max { σ , u h } from the search section.
Lemma 9.2 (The optimizer pays for maintenance). With this choice, both query terms equal Λ h ( σ ) \Lambda_h(\sigma) Λ h ( σ ) , while a + 3 v ≤ a + 4 v ≤ Λ h ( σ ) a+3v\le a+4v\le\Lambda_h(\sigma) a + 3 v ≤ a + 4 v ≤ Λ h ( σ ) . Moreover v < 1 / 16 v<1/16 v < 1/16 , so the inverse restriction holds with a constant margin for sufficiently small η \eta η .
Proof. Since κ ( 1 + u ) = 1 + σ \kappa(1+u)=1+\sigma κ ( 1 + u ) = 1 + σ , we have v = 1 − κ v=1-\kappa v = 1 − κ . It follows that b + 3 v = f + 2 v b+3v=f+2v b + 3 v = f + 2 v , and their common value is
( 1 + σ ) q h ( u ) + 3 u 1 + u − 3 σ . (1+\sigma)\frac{q_h(u)+3u}{1+u}-3\sigma. ( 1 + σ ) 1 + u q h ( u ) + 3 u − 3 σ .
The Rayleigh-quotient minimization in the preceding search section gives Λ h ( σ ) \Lambda_h(\sigma) Λ h ( σ ) at u = max { σ , u h } u=\max\{\sigma,u_h\} u = max { σ , u h } .
For σ ≤ u h \sigma\le u_h σ ≤ u h , write a h = u h / ( 1 + u h ) a_h=u_h/(1+u_h) a h = u h / ( 1 + u h ) . Direct substitution gives a h / χ h = ( S h − 1 ) / ( 6 S h ) < 1 / 12 a_h/\chi_h=(S_h-1)/(6S_h)<1/12 a h / χ h = ( S h − 1 ) / ( 6 S h ) < 1/12 , and hence
Λ h ( σ ) − ( a + 4 v ) = ( 1 + σ ) ( χ h − 5 a h ) + σ > 0. \Lambda_h(\sigma)-(a+4v)=(1+\sigma)(\chi_h-5a_h)+\sigma>0. Λ h ( σ ) − ( a + 4 v ) = ( 1 + σ ) ( χ h − 5 a h ) + σ > 0.
For σ ≥ u h \sigma\ge u_h σ ≥ u h , we have u = σ u=\sigma u = σ , κ = 1 \kappa=1 κ = 1 , a = σ a=\sigma a = σ , and v = 0 v=0 v = 0 . On the permitted interval, q h ( σ ) ≥ σ q_h(\sigma)\ge\sigma q h ( σ ) ≥ σ , proving the maintenance bound. Construction is cheaper than deletion because v ≥ 0 v\ge0 v ≥ 0 . Finally, u h < 1 / 16 u_h<1/16 u h < 1/16 because its numerator h 2 ( 1 − h 2 ) h^2(1-h^2) h 2 ( 1 − h 2 ) is at most 1 / 4 1/4 1/4 and its denominator is greater than 4 4 4 . On the first branch v ≤ u h v\le u_h v ≤ u h , and on the second branch v = 0 v=0 v = 0 . Thus 3 v < 3 / 16 < 1 + a 3v<3/16<1+a 3 v < 3/16 < 1 + a , leaving a fixed margin for 6 η 6\eta 6 η .
From fixed margins to one algorithm. Given any fixed ω > 0 \omega>0 ω > 0 , choose the geometric, rational-rounding, and construction margins so that their combined increase in the time exponent is below ω \omega ω . On the explicit branch, round the filter parameter downward to keep the implemented space parameter at most σ \sigma σ . The two branches are continuous and tangent where they meet. The resulting bounds are n Λ c ( σ ) + ω P n^{\Lambda_c(\sigma)+\omega}\mathcal{P} n Λ c ( σ ) + ω P time and n 1 + σ P n^{1+\sigma}\mathcal{P} n 1 + σ P space. The adaptive compiler gives the always-correct expected-prefix bound; capped construction and the phase schedule give worst-case Monte Carlo updates.
This family of algorithms, one for each fixed ω \omega ω , does not yet establish an o ( 1 ) o(1) o ( 1 ) term for a single algorithm. Appendix D specifies all margins as functions of n n n , bounds the finite-cover construction uniformly, and keeps the polynomial degrees fixed. It yields the explicit allowance O c , σ ( ( log ( 2 n ) ) − 1 / 100 ) O_{c,\sigma}((\log(2n))^{-1/100}) O c , σ (( log ( 2 n ) ) − 1/100 ) in Corollary 1.4, and therefore Theorem 1.3 .
Finite representations. The rational implementation computes centers by linear programs on sampled original lifted coordinates. Shell membership, scale eligibility, and the final weak-edge test use exact signed squared comparisons. Padding coefficients are rational, and normalized directions are represented by their unnormalized inputs. Gaussian approximations are sampled at polynomial precision for the Monte Carlo probability bounds; in the zero-error version, exact finite coverage tests establish correctness independently of this coupling. Label counts, ranks, and codes have polynomial bit length. Consequently the arithmetic bounds acquire only a polynomial factor in the coordinate bit length B B B . Each generation uses original input coordinates, so repeated rebuilding does not accumulate precision requirements.
AI Use Statement
This work involved extensive interaction with OpenAI Astra, including exploration of arguments and assistance with drafting and revising the manuscript. Gemini Argon also assisted with parts of the work. The authors directed the process and are responsible for the results, arguments, and final content.
Supplementary Lean files. The accompanying repository is https://github.com/hajiaghayi/Diameter-Alg1 .
Exact construction and certification of lifted centers
The geometric argument in § 5 needs a point of positive depth in the lifted space. It also needs a way to recover an actual data point whose distance realizes the variance bound. This appendix supplies both computational ingredients. We first construct a rational centerpoint from a small sample. We then turn a candidate center into a collection of disjoint, explicitly checked convex combinations. These combinations certify the distance inequalities even if the random centerpoint computation was unsuccessful. The finite-search certificates in Appendix § 12 will serve the same purpose for the angular and inverse-search structures.
Recall that z ∈ R D z \in\mathbb{R}^{D} z ∈ R D has depth at least α ∣ P ∣ \alpha|P| α ∣ P ∣ in P P P if every closed halfspace containing z z z contains at least α ∣ P ∣ \alpha|P| α ∣ P ∣ input identities. An α \alpha α -net for halfspaces is a sample that meets every halfspace containing at least an α \alpha α fraction of P P P . We count identities, so repeated coordinates cause no difficulty. A convex-hull certificate consists of nonnegative weights summing to one whose weighted sum is z z z . Disjoint groups with a common convex combination are often called Tverberg partitions; related constructions are studied in [21 ] .
For arbitrary real input in the arithmetic-RAM model, the first constructor may be replaced by Har-Peled–Jones [20 Theorem 18] . In dimension D D D , setting their constant accuracy parameter to 3 / 4 3/4 3/4 gives depth 1 / ( 4 ( D + 2 ) 2 ) 1/(4(D + 2)^2) 1/ ( 4 ( D + 2 ) 2 ) in O ( D 7 log 3 ( D + 2 ) log 3 ( 2 / φ ) ) O(D^7 \log^3(D + 2) \log^3(2/\varphi)) O ( D 7 log 3 ( D + 2 ) log 3 ( 2/ φ )) arithmetic operations, with failure probability at most φ \varphi φ and uniform sampling access. After lifting, D = d + 1 D = d + 1 D = d + 1 . The rational constructions below additionally bound the number of bits in all computed coordinates and permit exact verification. They use polynomial-time rational linear programming; no strongly polynomial algorithm for general linear programming is needed.
Why intersect sampled convex hulls? A sufficiently large random sample contains a fixed centerpoint in its convex hull. Intersecting several such hulls therefore gives a feasible linear program with high probability. Conversely, any point in their intersection is contained in a halfspace only if that halfspace meets every sampled group. Uniform convergence turns this sample count into a depth guarantee for the entire input.
Lemma A.1 (A polynomial-size exact centerpoint program). Given uniform sampling access to a nonempty identified population P ⊆ Q D P \subseteq\mathbb{Q}^{D} P ⊆ Q D with coordinate encoding length at most B B B , and 0 < φ < 1 / 2 0 < \varphi< 1/2 0 < φ < 1/2 , one can compute an exact rational α \alpha α -centerpoint with probability at least 1 − φ 1 - \varphi 1 − φ . Here α − 1 = poly ( D , log ( 1 / φ ) ) \alpha^{-1} = \operatorname{poly}(D, \log(1/\varphi)) α − 1 = poly ( D , log ( 1/ φ )) ; the sample size, running time, and output encoding length are polynomial in D D D , B B B , log ( 1 / φ ) \log(1/\varphi) log ( 1/ φ ) .
Proof. The proof has three parts: construct the intersection program, show that it is feasible, and show that every feasible solution has the required depth.
Sampling and the linear program. Put L = log ( 2 ( D + 2 ) / φ ) L = \log(2(D + 2)/\varphi) L = log ( 2 ( D + 2 ) / φ ) and choose a sufficiently large absolute constant C C C . Draw s s s independent uniform sample indices, where
s = ⌈ C ( D + 1 ) 2 L ⌉ , r = ⌈ C ( D + 1 ) s L ⌉ , s = \lceil C(D + 1)^2 L \rceil,\qquad r = \lceil C(D + 1)sL \rceil, s = ⌈ C ( D + 1 ) 2 L ⌉ , r = ⌈ C ( D + 1 ) s L ⌉ ,
and divide them into r r r blocks of s s s indices. Multiplicities are retained. Find a common point of their convex hulls by the program
z = ∑ j = 1 s λ i j p i j , ∑ j = 1 s λ i j = 1 , λ i j ≥ 0 ( 1 ≤ i ≤ r ) . (9) z = \sum_{j=1}^{s} \lambda_{ij}p_{ij},\qquad\sum_{j=1}^{s} \lambda_{ij} = 1,\qquad\lambda_{ij} \ge0\quad(1 \le i \le r). \tag*{(9)} z = j = 1 ∑ s λ ij p ij , j = 1 ∑ s λ ij = 1 , λ ij ≥ 0 ( 1 ≤ i ≤ r ) . (9)
Report failure if it is infeasible. Feasibility. The centerpoint theorem guarantees a point z ∗ z^* z ∗ of depth ∣ P ∣ / ( D + 1 ) |P|/(D+1) ∣ P ∣/ ( D + 1 ) in P P P . A halfspace 1 / ( D + 1 ) 1/(D+1) 1/ ( D + 1 ) -net of P P P has z ∗ z^* z ∗ in its convex hull, by strict separation. The halfspace-net theorem [22 ] implies that one block is such a net with failure at most φ / ( 2 r ) \varphi/(2r) φ / ( 2 r ) ; the stated s s s suffices because log ( r / φ ) = O ( L ) \log(r/\varphi)=O(L) log ( r / φ ) = O ( L ) . Thus the program is feasible with probability at least 1 − φ / 2 1-\varphi/2 1 − φ /2 .
Depth of every feasible solution. Let μ ( H ) = ∣ P ∩ H ∣ / ∣ P ∣ \mu(H)=|P\cap H|/|P| μ ( H ) = ∣ P ∩ H ∣/∣ P ∣ be the fraction of input identities in a halfspace H H H , and let μ ^ ( H ) \widehat{\mu}(H) μ ( H ) be the corresponding fraction among all r s rs r s sampled occurrences. The VC uniform-convergence theorem for halfspaces gives, with probability at least 1 − φ / 2 1-\varphi/2 1 − φ /2 ,
sup H ∣ μ ^ ( H ) − μ ( H ) ∣ ≤ 1 2 s , \sup_H \left|\widehat{\mu}(H)-\mu(H)\right| \le\frac{1}{2s}, H sup ∣ μ ( H ) − μ ( H ) ∣ ≤ 2 s 1 ,
provided r s ≥ C 0 s 2 ( ( D + 1 ) log ( s + 1 ) + log ( 2 / φ ) ) rs \ge C_0s^2((D+1)\log(s+1)+\log(2/\varphi)) r s ≥ C 0 s 2 (( D + 1 ) log ( s + 1 ) + log ( 2/ φ )) ; our choices meet this inequality [30 ] . Every closed halfspace containing a feasible z z z meets each block, so its empirical mass is at least r / ( r s ) = 1 / s r/(rs)=1/s r / ( r s ) = 1/ s . Its original mass is therefore at least 1 / ( 2 s ) 1/(2s) 1/ ( 2 s ) . Set α = 1 / ( 2 s ) \alpha=1/(2s) α = 1/ ( 2 s ) . These two events hold simultaneously with probability at least 1 − φ 1-\varphi 1 − φ by a union bound. The uniform statement applies to the solution selected by the program, even though that solution depends on the entire sample.
Exact arithmetic. The program has polynomially many variables and only original input coordinates as nonconstant coefficients. Exact rational linear programming gives both the stated running time and polynomial output precision [18 ] . In particular, no long sequence of geometric eliminations can inflate the coordinates of the center. For a failed or infeasible attempt the dynamic structure uses its deterministic contraction fallback; no depth claim is made then. □
From a likely center to a verifiable certificate. A sampled center can be wrong, but a displayed convex combination can be checked exactly. We therefore partition the original birth pool into disjoint groups and retain only groups whose lifted convex hulls contain the candidate center. Accepting sufficiently many groups proves the needed depth deterministically. Disjointness is crucial: one deletion can invalidate at most one retained group.
Lemma A.2 (Checked disjoint block certificates). There is s 0 = poly ( d ) s_0=\operatorname{poly}(d) s 0 = poly ( d ) such that, on a birth pool P 0 P_0 P 0 of m ≥ 2 s 0 m\ge2s_0 m ≥ 2 s 0 rational points, a Las Vegas algorithm returns z = ( o , s ) z=(o,s) z = ( o , s ) and at least m / ( 4 s 0 ) m/(4s_0) m / ( 4 s 0 ) disjoint blocks of exactly s 0 s_0 s 0 birth identities whose lifted convex hulls contain z z z . It returns exact rational convex coefficients for every block. The expected construction time is m poly ( d , B ) m\operatorname{poly}(d,B) m poly ( d , B ) , with m poly ( d , B ) m\operatorname{poly}(d,B) m poly ( d , B ) space on every outcome and polynomial coordinate and coefficient encoding length. Every returned certificate is correct, and the algorithm terminates almost surely.
Proof. We generate a candidate, verify it against disjoint groups, and repeat only when too few groups pass. The verification gives correctness; the probability analysis bounds the expected number of attempts.
Candidate and group size. In dimension D = d + 1 D=d+1 D = d + 1 , first use Lemma A.1 with failure probability 1 / 10 1/10 1/10 . With probability at least 9 / 10 9/10 9/10 its candidate has depth α 0 = 1 / poly ( D ) \alpha_0=1/\operatorname{poly}(D) α 0 = 1/ poly ( D ) in the lifted pool. Choose
s 0 = ⌈ C α 0 − 1 ( ( D + 1 ) log ( 2 / α 0 ) + 1 ) ⌉ . s_0=\left\lceil C\alpha_0^{-1}\bigl((D+1)\log(2/\alpha_0)+1\bigr)\right\rceil. s 0 = ⌈ C α 0 − 1 ( ( D + 1 ) log ( 2/ α 0 ) + 1 ) ⌉ .
A uniform s 0 s_0 s 0 -element subset is an α 0 \alpha_0 α 0 -net for halfspaces with probability at least 9 / 10 9/10 9/10 . This follows also from the usual sampling-with-replacement theorem: discard repetitions and fill the sample with uniformly chosen unused identities. The resulting set is uniform, and adding points preserves the net property.
Exact verification. Take a fresh random permutation of the birth identities and partition its first r s 0 rs_0 r s 0 positions into r = ⌊ m / s 0 ⌋ r = \lfloor m/s_0 \rfloor r = ⌊ m / s 0 ⌋ blocks. For each block solve (9) with z z z now fixed, using the lifted coordinates. Accept the attempt only if at least ⌈ r / 2 ⌉ \lceil r/2 \rceil ⌈ r /2 ⌉ blocks pass. Otherwise restart the entire attempt.
Expected number of attempts. Conditioned on a genuinely deep candidate, each block fails with probability at most 1 / 10 1/10 1/10 . Markov’s inequality, without any independence between blocks, shows that at least half pass with probability at least 4 / 5 4/5 4/5 . An attempt therefore succeeds with probability greater than 1 / 2 1/2 1/2 . Each attempt costs m poly ( d , B ) m \operatorname{poly}(d,B) m poly ( d , B ) and uses the stated space; fresh retries give the expected bound and almost-sure termination.
Validity of an accepted answer. Every accepted block is checked by an exact LP, whether or not the candidate was deep. Since m ≥ 2 s 0 m \ge2s_0 m ≥ 2 s 0 , the number retained is at least m / ( 4 s 0 ) m/(4s_0) m / ( 4 s 0 ) . The LPs use original lifted coordinates and the one candidate, so their rational output lengths remain polynomial.
Example and behavior under deletions. For four points ( 1 , 0 ) , ( − 1 , 0 ) , ( 0 , 1 ) , ( 0 , − 1 ) (1,0),(-1,0),(0,1),(0,-1) ( 1 , 0 ) , ( − 1 , 0 ) , ( 0 , 1 ) , ( 0 , − 1 ) in the plane, the two opposite pairs are disjoint groups. Their lifts both have z = ( 0 , 0 , 1 ) z=(0,0,1) z = ( 0 , 0 , 1 ) as their midpoint. Thus the two pairs certify the same center o = ( 0 , 0 ) o=(0,0) o = ( 0 , 0 ) and variance V = 1 V=1 V = 1 . Deleting one input point invalidates only its pair; the other pair remains an exact certificate. The construction above gives many such disjoint certificates in higher dimensions, without requiring symmetry.
These certificates establish depth β m \beta m β m , where β = 1 / ( 4 s 0 ) \beta= 1/(4s_0) β = 1/ ( 4 s 0 ) , without a probability qualification: every closed halfspace through z z z meets every retained block. They also prove V = s − ∥ o ∥ 2 ≥ 0 V=s-\lVert o\rVert^2 \ge0 V = s − ∥ o ∥ 2 ≥ 0 and (3) directly from their coefficients. During at most β m / 16 \beta m/16 β m /16 input changes, at least 15 β m / 16 15\beta m/16 15 β m /16 blocks remain intact. Each supplies a core point and an exact witness for every query. Inserted identities are never added to an old certificate, and a reinsertion receives a new lifetime, so it cannot revive an invalidated block.
Failure probabilities and rebuilds. For the finite-horizon structure, fix the per-construction probability before defining the depth. A choice φ = δ / ( n + t + d + B + 1 ) C \varphi= \delta/(n+t+d+B+1)^C φ = δ / ( n + t + d + B + 1 ) C with sufficiently large constant C C C dominates the polynomial number of centers and witness samples in the scheduled construction; the final composition includes all its additional parameters in this denominator. This avoids a circular choice involving the random hierarchy depth. For the zero-error structure, the constructor above has constant success probability independently of the current history, and requires no horizon. Conditional expected rebuild costs can therefore be charged to the deterministic local lifetimes. Randomness affects only construction time, not any accepted geometric certificate or cached pair.
Exact certificates and finite representations
The zero-error structure must justify two statements by finite tests: every target angular pair shares a filter label, and an inverse query recovers every input with its requested label. A high-probability claim for a fixed query would not suffice, because future queries may depend on the accepted random choices.
We first check angular coverage on a sufficiently fine finite net. A margin in each inequality extends the checked statement to every point on the sphere. We then explain how to represent the rotations and comparisons exactly on rational input. Finally, we certify inverse recovery by comparing the query routine’s output with the exact fibers in small batches. These are the implementation details used in Proposition 6.4 and Lemma 6.5 . Gaussian probability estimates bound expected work; correctness follows from the accepted certificates on every outcome.
The finite splitter and the small-sphere certificate
A direct net of the whole sphere would be too large. We first divide a moderate-dimensional block into small blocks, using a finite family of linear maps that includes a suitable map for every relevant pair. We can then afford to check a net in each small block. Recall the angular parameters: a target pair has inner product at least h > 0 h > 0 h > 0 , the data and query thresholds are t t t and x t xt x t , and h ≤ x ≤ 1 h \le x \le1 h ≤ x ≤ 1 . Here t t t denotes the Gaussian threshold, independently of the execution horizon elsewhere in the paper.
Finite norm splitters. For moderate dimension B 0 B_0 B 0 and small dimension b b b , both powers of four, let s = B 0 / b s = B_0/b s = B 0 / b . The splitting family in Wei [31 Proposition 11] can be represented exactly. At a halving step, pair coordinates by a two-wise independent permutation and take signed sums and differences divided by 2 \sqrt{2} 2 , using four-wise independent signs. The variance of a rescaled squared norm is O ( 1 / k ) O(1/k) O ( 1/ k ) when the smaller dimension is k k k . Chebyshev’s inequality and a union bound over three vectors give a seed preserving both halves with error O ( k − 1 / 2 ) O(k^{-1/2}) O ( k − 1/2 ) . Recurse on both halves. Along a path the errors sum to O ( b − 1 / 2 ) O(b^{-1/2}) O ( b − 1/2 ) , and the number of finite seed choices is exp ( O ( s log B 0 ) ) \exp(O(s \log B_0)) exp ( O ( s log B 0 )) . Affine permutations and degree-three sign hashes give explicit seed families. Every final matrix is an integer matrix times s − 1 / 2 s^{-1/2} s − 1/2 , which is rational because s s s is a power of four. The gate tests use squared norms exactly.
A finite test for coverage of a small sphere. Fix one small block. Write ϵ = 1000 / b \epsilon= 1000/\sqrt{b} ϵ = 1000/ b and t 0 = t / s t_0 = t/\sqrt{s} t 0 = t / s ; the cutoff ensures ϵ < h / 10 \epsilon< h/10 ϵ < h /10 and t 0 ≥ 1 t_0 \ge1 t 0 ≥ 1 . Use the finite net
Z = { a / ∥ a ∥ : a ∈ Z b ∖ { 0 } , ∣ a i ∣ ≤ b 3 } . Z = \{a/\lVert a\rVert: a \in\mathbb{Z}^{b} \setminus\{0\},\ |a_i| \le b^3\}. Z = { a / ∥ a ∥ : a ∈ Z b ∖ { 0 } , ∣ a i ∣ ≤ b 3 } .
Rounding b 3 z b^3z b 3 z coordinatewise and renormalizing gives net error at most ν = b − 2 \nu= b^{-2} ν = b − 2 . Thus log ∣ Z ∣ = O ( b log b ) \log|Z| = O(b \log b) log ∣ Z ∣ = O ( b log b ) . Choose rational G = O ( log m ) G = O(\sqrt{\log m}) G = O ( log m ) so that an ideal b b b -dimensional Gaussian has norm greater than G / 2 G/2 G /2 with probability at most m − 100 m^{-100} m − 100 . A sampled family is accepted only if every coefficient vector has norm at most G G G and every ordered net pair of correlation at least h − 3 ϵ h - 3\epsilon h − 3 ϵ has one vector g g g satisfying
⟨ g , v 0 ⟩ ≥ t 0 + 2 G ν , ⟨ g , z 0 ⟩ ≥ x t 0 + 2 G ν . \langle g,v_0\rangle\ge t_0 + 2G\nu,\qquad\langle g,z_0\rangle\ge xt_0 + 2G\nu. ⟨ g , v 0 ⟩ ≥ t 0 + 2 G ν , ⟨ g , z 0 ⟩ ≥ x t 0 + 2 G ν .
The stronger thresholds reserve room for replacing an arbitrary sphere point by its nearest net point. All these tests are exact algebraic comparisons. A pair of correlation at least h − 2 ϵ h - 2\epsilon h − 2 ϵ rounds to a checked pair because 2 ν ≤ ϵ 2\nu\le\epsilon 2 ν ≤ ϵ . The norm cap changes each inner product by at most G ν G\nu G ν , proving coverage at the original thresholds. This argument is deterministic.
Why a random family passes with constant probability. We next bound the number of sampled cap vectors needed by this finite test. This bound controls construction time and does not enter the deterministic coverage argument. Put
a = h − 3 ϵ , c h = 2 − ⌈ 100 / ( 1 − h ) ⌉ , p 0 = c h t 0 − 2 exp ( − I a ( x ) t 0 2 / 2 ) . a = h - 3\epsilon,\qquad c_h = 2^{-\lceil100/(1-h)\rceil},\qquad p_0 = c_h t_0^{-2}\exp(-I_a(x)t_0^2/2). a = h − 3 ϵ , c h = 2 − ⌈ 100/ ( 1 − h )⌉ , p 0 = c h t 0 − 2 exp ( − I a ( x ) t 0 2 /2 ) .
For correlation a a a , integrate the Gaussian density over [ t 0 + 1 / t 0 , t 0 + 2 / t 0 ] × [ x t 0 + 1 / t 0 , x t 0 + 2 / t 0 ] [t_0+1/t_0,t_0+2/t_0]\times[xt_0+1/t_0,xt_0+2/t_0] [ t 0 + 1/ t 0 , t 0 + 2/ t 0 ] × [ x t 0 + 1/ t 0 , x t 0 + 2/ t 0 ] . At ( t 0 , x t 0 ) (t_0,xt_0) ( t 0 , x t 0 ) both density-exponent derivatives lie in [ 0 , t 0 ] [0,t_0] [ 0 , t 0 ] , since a ≤ x ≤ 1 a\le x\le1 a ≤ x ≤ 1 . Across the rectangle the linear and quadratic increases are at most 4 4 4 and 4 / ( 1 − h ) 4/(1-h) 4/ ( 1 − h ) . Its area is t 0 − 2 t_0^{-2} t 0 − 2 and the density prefactor is at least 1 / ( 2 π ) 1/(2\pi) 1/ ( 2 π ) . Thus p 0 p_0 p 0 is a conservative lower bound. Joint-cap probability increases with correlation. The cutoff also ensures 3 G ν ≤ 1 / t 0 3G_\nu\le1/t_0 3 G ν ≤ 1/ t 0 , so this lower bound covers the stronger thresholds with 3 G ν 3G_\nu 3 G ν in place of 2 G ν 2G_\nu 2 G ν .
Compute rational p r a t ∈ [ p 0 / 2 , p 0 ] p_{\mathrm{rat}}\in[p_0/2,p_0] p rat ∈ [ p 0 /2 , p 0 ] by certified exponential evaluation, set L 0 = ⌈ log 2 ( 2 ∣ Z ∣ ) ⌉ L_0=\lceil\log_2(2|\mathcal{Z}|)\rceil L 0 = ⌈ log 2 ( 2∣ Z ∣ )⌉ , and sample
M 0 = ⌈ 32 L 0 p r a t ⌉ M_0=\left\lceil\frac{32L_0}{p_{\mathrm{rat}}}\right\rceil M 0 = ⌈ p rat 32 L 0 ⌉
vectors. A union bound over net pairs gives ideal acceptance probability at least 9 / 10 9/10 9/10 . Use finite Gaussian coefficients whose coordinate error is at most m − 40 m^{-40} m − 40 except with probability m − 100 m^{-100} m − 100 per coordinate. Their errors are smaller than the reserved threshold margin. Since M 0 = m o ( 1 ) M_0=m^{o(1)} M 0 = m o ( 1 ) , the norm and coupling events hold jointly with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , and the exact certificate accepts with probability at least 1 / 2 1/2 1/2 . Verification takes M 0 ∣ Z ∣ 2 poly ( b , log m ) = m o ( 1 ) M_0|\mathcal{Z}|^2\operatorname{poly}(b,\log m)=m^{o(1)} M 0 ∣ Z ∣ 2 poly ( b , log m ) = m o ( 1 ) time and space. All failed attempts have this same space bound and are discarded before the next attempt.
Expected label counts after acceptance. For a fixed full label, conditioning its s s s independent base families on these certificates increases probabilities by at most 2 s 2^s 2 s . Apply this bound to the finite unconditioned law first, then couple the selected coefficients to independent ideal Gaussians. The finite law is sampled by a clipped rational inverse-normal transform on a uniform integer grid; monotonicity and certified function evaluation supply the stated coupling and deterministic coefficient-length bounds. For any fixed pair, coefficient error only shifts the final positive thresholds by m − O ( 1 ) m^{-O(1)} m − O ( 1 ) . Gaussian tail estimates therefore change by a subpolynomial factor. There are at most m 3 m^3 m 3 raw labels per moderate index above the cutoff; the coupling exception contributes negligibly even after summing all label occurrences. These are fixed-pair moment estimates, not an assertion that one continuous coupling covers every direction. Continuum coverage already follows from the exact finite certificate.
Exact rotations and bounded-degree comparisons
The preceding certificate assumes exact inner products and exact orthogonal decompositions. Rounding the entries of an orthogonal matrix independently would destroy orthogonality, so it would also destroy the deterministic target-coverage argument. We instead round vectors that define reflections and apply the reflection formula exactly. We first establish exact orthogonality, then compare the resulting distribution with an ideal random rotation to bound work, and finally bound the cost of all algebraic comparisons.
Exact orthogonality from rational reflections. A Haar rotation is an orthogonal matrix drawn from the rotationally invariant probability distribution. Generate such a rotation recursively from Gaussian directions and Householder completions. For a unit direction u u u , choose a stable sign s ∈ { − 1 , 1 } s\in\{-1,1\} s ∈ { − 1 , 1 } agreeing with the sign of its first coordinate, form w ∗ = u + s e 1 w_\ast=u+se_1 w ∗ = u + s e 1 , and use H ( w ∗ ) D s H(w_\ast)D_s H ( w ∗ ) D s , where
D s = diag ( − s , 1 , … , 1 ) . D_s=\operatorname{diag}(-s,1,\ldots,1). D s = diag ( − s , 1 , … , 1 ) .
Indeed, H ( w ∗ ) e 1 = − s u H(w_\ast)e_1=-su H ( w ∗ ) e 1 = − s u , so the diagonal factor makes the first column equal to u u u . Approximate each Householder vector by a rational vector w w w , keep D s D_s D s exactly, and apply
H ( w ) = I − 2 w w T / ( w T w ) H(w)=I-2ww^{\mathsf{T}/(w^{\mathsf{T}}w)} H ( w ) = I − 2 w w T / ( w T w )
exactly. If a rounded vector is zero, use a fixed nonzero vector. Each actual factor, and hence the full product, is exactly orthogonal. Coverage of a positive pair therefore cannot fail.
Comparison with the ideal random rotation. The comparison is needed only for the expected-work estimates. For the distributional comparison, the stable vector’s norm is at least one. The sign may be chosen from a sufficiently accurate approximation to u 1 u_1 u 1 ; if a near-zero first coordinate changes its sign, the norm is still bounded below by an absolute constant. Choose the same sign in the ideal completion, including its diagonal factor; conditional on its first column, any such orthogonal completion followed by an independent Haar rotation of the complement has the Haar law. On the event that all Gaussian norms exceed m − C D − C m^{-C}D^{-C} m − C D − C and all coordinates have polynomially bounded magnitude, these operations are polynomially Lipschitz. Gaussian small-ball and tail bounds make the exceptional probability at most m − A m^{-A} m − A for any prescribed constant A A A . Polynomially many bits thus couple the rational product to the ideal one with operator error at most δ / ( 100 D ) \delta/(100\sqrt{D}) δ / ( 100 D ) . Moderate block norms are Ω ( B 0 / D ) \Omega(\sqrt{B_0/D}) Ω ( B 0 / D ) on the projection event, so normalization changes correlations by less than the reserved negative margin.
Bit length of the represented rotation. Each factor is rounded on a fixed precision grid before its exact Householder formula is applied. It has a polynomial-length common denominator. A product of D D D such factors has denominator length at most the sum of their lengths, and numerator growth adds only O ( D log D ) O(D\log D) O ( D log D ) bits. This prevents denominator growth from being hidden in a repeated normalization operation. Projection concentration uses B 0 = Θ ( δ − 2 log m ) B_0=\Theta(\delta^{-2}\log m) B 0 = Θ ( δ − 2 log m ) ; there is no exponential dependence on 1 / δ 1/\delta 1/ δ in this implementation.
Exact comparisons without repeated normalization. All vector tests can be made without storing normalized coordinates. For example, the common padding maps a rational direction record v ≠ 0 v\ne0 v = 0 to ( α v / ∥ v ∥ , β ) (\alpha v/\lVert v\rVert,\beta) ( α v / ∥ v ∥ , β ) with rational α , β \alpha,\beta α , β . A cap test is
α ⟨ g , v ⟩ ≥ ( t − β g d + 1 ) ∥ v ∥ , \alpha\langle g,v\rangle\ge(t-\beta g_{d+1})\lVert v\rVert, α ⟨ g , v ⟩ ≥ ( t − β g d + 1 ) ∥ v ∥ ,
decidable by signs and a squared rational comparison. After multiplying by r \sqrt{r} r , where r = ∥ v ∥ 2 r=\lVert v\rVert^2 r = ∥ v ∥ 2 , rational rotations and splitter maps leave coordinates of the form A + B r A+B\sqrt{r} A + B r . Gate denominators cancel in squared norm ratios. In a final normalized cap test, move the one positive norm to the other side and square only after its sign is known. Thus each vector remains in one fixed-degree field; no compositum is formed across the dimension. Net-pair and original weak-edge comparisons involve only a constant number of such radicals. A conservative degree bound of 32 suffices for the complete implementation, and coefficient lengths are polynomial in input length, dimension, and logarithmic parameters. Exact root isolation or successive sign-and-square comparisons give polynomial time. Every generation starts from original rational records and its rational center; a normalized output is never reused as a new input record. Coordinate precision therefore does not accumulate along the dynamic hierarchy.
Certifying actual inverse recovery in small workspace
An inverse structure must recover a complete fiber, not merely a point that appeared somewhere in a sampled chain. We verify the actual recovery routine on every output name, while using only the workspace allowed by the theorem. This gives a direct repair implementation of Lemma 6.5 . Recall that a fiber of a function F F F at y y y is F − 1 ( y ) = { i : F ( i ) = y } F^{-1}(y)=\{i:F(i)=y\} F − 1 ( y ) = { i : F ( i ) = y } . The derived function F 0 ′ F'_0 F 0 ′ has domain of size O ( M ) O(M) O ( M ) , each nonnull fiber has at most τ \tau τ members, and one evaluation costs E E E . A null value, denoted by ⊥ \perp ⊥ , records an inactive virtual input.
Recover exact fibers in batches. Freeze the derived bounded-fiber function F 0 ′ F'_0 F 0 ′ and retain the prescribed raw chains from [8 Section 4.3.1] , initially without a repair list. Process derived output names in batches of Θ ( M / τ 2 ) \Theta(M/\tau^2) Θ ( M / τ 2 ) . A full virtual-domain scan stores all fibers for one batch within O ( M / τ ) O(M/\tau) O ( M / τ ) space, since each fiber has at most τ \tau τ members. There are O ( τ 2 ) O(\tau^2) O ( τ 2 ) scans, costing O ~ ( M τ 2 E ) \widetilde{O}(M\tau^2E) O ( M τ 2 E ) .
Treat null inputs separately. The source handles null explicitly inside each chain hash. With M ′ M' M ′ the constant-padded derived domain, take g : [ 2 M ′ ] → [ M ′ ] g:[2M']\to[M'] g : [ 2 M ′ ] → [ M ′ ] and iterate
H ( i ) = { g ( F 0 ′ ( i ) ) , F 0 ′ ( i ) ≠ ⊥ , g ( M ′ + i ) , F 0 ′ ( i ) = ⊥ . H(i)=\begin{cases}
g(F'_0(i)), & F'_0(i)\ne\perp,\\
g(M'+i), & F'_0(i)=\perp.
\end{cases} H ( i ) = { g ( F 0 ′ ( i )) , g ( M ′ + i ) , F 0 ′ ( i ) = ⊥ , F 0 ′ ( i ) =⊥ .
Thus the null inputs have private tags before hashing; an arbitrary null fiber does not become a high-indegree chain vertex. This is exactly the null convention in [8 Section 4.3.1] .
Check recovery and store only omissions. For each name y y y , run its capped raw-chain recovery, validate each reported identity by F 0 ′ ( i ) = y F'_0(i)=y F 0 ′ ( i ) = y , remove duplicates, and compare with its exact stored fiber. Add exactly the missing identities to a repair dictionary keyed by y y y . Recovery starts at g ( y ) g(y) g ( y ) under the preceding chain map; the validation is on the original derived value y y y . This fixes the composition convention at chain endpoints and collisions. Reject an attempt when the repair dictionary exceeds C M / τ CM/\tau C M / τ identities. The fixed-target bounds of [8 Lemmas 24–25] imply an expected O ( M / τ ) O(M/\tau) O ( M / τ ) missing identities for these actual recoveries, so sufficiently large C C C leaves constant acceptance probability.
Correctness and resource bounds. Every accepted raw-query-plus-repair structure now returns each complete fiber deterministically. All O ( M ) O(M) O ( M ) recovery checks cost O ~ ( M τ 3 E ) \widetilde{O}(M\tau^3E) O ( M τ 3 E ) , while batches, raw chains, repairs, and one duplicate buffer use O ~ ( M / τ ) \widetilde{O}(M/\tau) O ( M / τ ) space. No forward array of length M M M is used in this regime. For τ < C log 2 ( 2 M ) \tau<C\log^2(2M) τ < C log 2 ( 2 M ) one may instead store explicit inverse lists: M = O ~ ( M / τ ) M=\widetilde{O}(M/\tau) M = O ( M / τ ) , and oracle evaluations and virtual identities contribute only logarithmic factors. Thus this small parameter case does not increase the final space exponent.
Dynamic schedules and zero-error accounting
This appendix supplies the construction schedules and adaptive running-time argument used in Section § 7 . There are three separate tasks. First, a new inverse phase must be constructed and brought up to date while the old phase is still valid. Second, an entire center chain must be replaced without exhausting the age budget of its small residuals. Third, the expected-time analysis must remain valid when later updates depend on exposed random choices. The next three subsections address these tasks in that order.
A certified inverse with worst-case maintenance
The clock in this subsection counts value deletions : one tick sets the forward-map value of one virtual identity to null. An external point deletion can produce up to R R R such ticks, all completed before the next query is exposed. The inverse parameter τ \tau τ controls the space–time tradeoff and is distinct from the number of external updates. We first schedule a single virtual inverse, then account for these R R R virtual changes and for replay during the outer frozen-generation build.
The implicit search lemma supplies the following phase interface. For a virtual domain of size M M M , parameter τ ≤ M 1 / 3 \tau\le M^{1/3} τ ≤ M 1/3 , and forward-evaluation time E E E , a verified immutable inverse can be built in expected O ~ ( M τ 3 E ) \widetilde{O}(M\tau^{3}E) O ( M τ 3 E ) time and O ~ ( M / τ ) \widetilde{O}(M/\tau) O ( M / τ ) space. Between reconstructions it processes a value deletion in D = O ~ ( τ 3 E ) D = \widetilde{O}(\tau^{3}E) D = O ( τ 3 E ) worst-case time and answers predicate searches with the proved ( Q , F ) (Q,F) ( Q , F ) bound. It remains valid for a phase containing a constant multiple of M / τ M/\tau M / τ value deletions. All fibers used by a completed phase are certified, so these statements are deterministic once construction finishes.
For a finite horizon, cap one complete construction attempt at a sufficiently large constant times its conditional expectation. This cap includes every retry, verification, and cleanup operation. Markov’s inequality gives success probability at least 1 / 2 1/2 1/2 . Run K K K independent capped attempts, sequentially, and retain the first success. The resulting budget is B 0 = O ~ ( K M τ 3 E ) B_0 = \widetilde{O}(KM\tau^{3}E) B 0 = O ( K M τ 3 E ) , with failure at most 2 − K 2^{-K} 2 − K . The same rule is applied to the entire certified-family and point-assignment constructor, not only to the inverse. Conditioning on one accepted birth group inflates the required geometric moments by a constant factor. Later phase failures are union bounded separately; we never condition those moments on every future rebuild succeeding.
Lemma C.1 (Pipelined inverse phases). With the preceding capped constructor, one current value deletion uses O ~ ( K τ 4 E ) \widetilde{O}(K\tau^{4}E) O ( K τ 4 E ) worst-case work and O ~ ( M / τ ) \widetilde{O}(M/\tau) O ( M / τ ) total space. Except when a cap fails, every phase oracle and every answer remain exact.
Proof. The construction has three stages: retain an immutable birth oracle, build the new inverse against that oracle, and replay the intervening deletions before switching service to the new phase. The overlap is short enough that the serving phase remains valid throughout.
Let H = ⌊ M / ( 64 τ ) ⌋ H = \lfloor M/(64\tau) \rfloor H = ⌊ M / ( 64 τ )⌋ , increasing the fixed small-instance cutoff if necessary. Start a new phase every H H H value-deletion ticks. Its immutable oracle is the function at its starting tick. While construction runs, store the first old value of every changed identity in a dictionary. An oracle call consults that dictionary before the current function, exactly reconstructing the immutable snapshot. Give the constructor ⌈ 8 B 0 / H ⌉ \lceil8B_0/H \rceil ⌈ 8 B 0 / H ⌉ work per tick, so it finishes within H / 4 H/4 H /4 ticks.
Next replay the queued deletions, with work for four deletions per tick. New arrivals append to the queue. The replay oracle returns null on applied deletions, the saved old value on unapplied deletions, and the current value elsewhere. Mark a deletion applied before notifying the new inverse. This order ensures that any reconstruction triggered by that notification sees the correct intermediate function. A backlog of at most H / 4 H/4 H /4 drains within H / 2 + 1 H/2+1 H /2 + 1 further ticks. The new phase is ready before H / 2 H/2 H /2 ticks and can replace the old one before its age reaches 3 H / 2 3H/2 3 H /2 . This lies within its validity interval.
At most two phases and their retirement work coexist. Their old-value dictionaries, replay queues, and sparse bucket remnants have O ( H ) = O ( M / τ ) O(H) = O(M/\tau) O ( H ) = O ( M / τ ) records. Construction contributes O ( B 0 / H ) = O ~ ( K τ 4 E ) O(B_0/H) = \widetilde{O}(K\tau^{4}E) O ( B 0 / H ) = O ( K τ 4 E ) work per tick, and replay contributes O ( D ) O(D) O ( D ) . A failed cap disables that copy within the same resource bound; it is an error event, not an unbounded computation. □ \square □
An original point has at most R R R virtual ranks. Delete them in order using one pending point and one rank cursor. Record each old value in every applicable snapshot log, then advance the cursor before notifying the inverse; only after the last notification mark the point inactive in this generation. Queries do not interleave with this operation. The point’s coordinates and label metadata remain accessible to every phase that still refers to them. Thus the worst-case original-deletion bound is O ~ ( R K τ 4 E ) \widetilde{O}(RK\tau^{4}E) O ( R K τ 4 E ) , without a bitmap of size m R mR m R .
There is also an outer replay when a frozen insertion interval is constructed. Retain its persistent root in constant time. Its birth oracle remains immutable throughout initialization; arriving deletions are queued by original lifetime identity , even before the scan has assigned its local point number. After initialization, replay those deletions using an arrival/applied bitmap and the single rank cursor. An arrival does not change this internal current oracle until replay applies it. There are at most m m m original deletions. The initial build and all possible replay therefore cost at most C m A ( n ) P CmA(n)P C m A ( n ) P . Give the job a sufficiently large multiple of A ( n ) P A(n)P A ( n ) P per outer tick and declare it ready as soon as initialization is complete and its queue is empty. Every tick while it is unready pays useful work, so it finishes within m ≤ w m \le w m ≤ w ticks. This proves the constructor deadline required by Lemma 7.1 .
Replacing a chain without aging its small residuals
A replacement chain may contain pools much smaller than its root. If every center were sampled when the root job started, a small residual could exhaust its age budget before the whole chain became ready. We therefore open each residual level only when the time remaining until activation is proportional to that residual’s own size.
Here a clock tick of a pool is an external point insertion or deletion in that pool, rather than a virtual value deletion. Unaffected pools receive no tick. Let α \alpha α be the depth parameter, C C C the polynomial cost of computing a fresh center from a sampled persistent snapshot, and K 0 K_{0} K 0 the polynomial number of fresh samples for a baseline witness. Set C ∗ = 4096 C_{\ast}=4096 C ∗ = 4096 and choose a polynomial leaf cutoff L L L satisfying
L ≥ 2 20 C ∗ α − 2 , L ≥ C + ( d + log n ) K 0 + 64 α − 1 . (10) L \ge2^{20}C_{\ast}\alpha^{-2}, \qquad L \ge C + (d+\log n)K_{0} + 64\alpha^{-1}. \tag*{(10)} L ≥ 2 20 C ∗ α − 2 , L ≥ C + ( d + log n ) K 0 + 64 α − 1 . (10)
Small leaves are handled exactly.
A serving node born with M M M input points starts one replacement job at age ⌊ α M / 64 ⌋ \lfloor\alpha M/64 \rfloor ⌊ α M /64 ⌋ . If its current input size is m > 4 L m > 4L m > 4 L , give the job a deadline H = ⌊ α m / C ∗ ⌋ H=\lfloor\alpha m/C_{\ast}\rfloor H = ⌊ α m / C ∗ ⌋ further root-pool ticks; otherwise replace the suffix immediately by an exact leaf. The old node’s age at this deadline is less than α M / 16 \alpha M/16 α M /16 , so it remains valid. Only serving nodes own jobs. A pending job consists of a completed prefix of fixed balls and one current residual; it starts no nested replacement jobs inside that prefix.
If r r r ticks remain and the residual currently has m m m points, open its next level only when r ≤ α m / C ∗ r \le\alpha m/C_{\ast} r ≤ α m / C ∗ . For m ≤ 2 L + 1 m \le2L+1 m ≤ 2 L + 1 , close it as a leaf. Otherwise retain its birth snapshot, compute a center immediately in the opening update, and build its radius dictionary and local search indices in the background. If the sampled program reports infeasibility, or the returned center has V < 0 V < 0 V < 0 , first choose any birth point as o o o and provisional V = 0 V=0 V = 0 . Check explicitly that the birth core contains at least α m / 2 \alpha m/2 α m /2 points. If a Monte Carlo center fails that check, use the same first-coordinate center with the maximum birth radius as the ball; this preserves contraction and all work bounds even on a failure outcome. Correctness is asserted on the good center event.
The scans and their updates. Each pool is a persistent balanced tree, with subtree sizes for uniform rank sampling. A first scan counts the birth core, finds the maximum birth radius, and indexes current radii. The first two statistics examine every immutable birth record, even if its lifetime has since ended. Each lifetime has separate generation-local heap-indexed and classified flags. For the current radius dictionary, delete a record only if heap-indexed, index new insertions immediately, and skip a scanned insertion if its lifetime is dead or already heap-indexed. Once the ball is fixed, retain a snapshot of the then-current input and scan it to classify its exact outside-ball child and construct the local angular records. An active record is classified only if its classified flag is unset. Concurrent insertions are classified immediately; deletions remove classified records. Commit both matching copies in every applicable configuration, the child entry, and the classified flag within one external update. Each local insertion invokes the fully dynamic search interface, whose own flat jobs are included in its operation bound.
Over b b b root ticks, these scans and arriving changes take O ( ( m + b ) A ( n ) P ) O((m+b)A(n)\mathcal{P}) O (( m + b ) A ( n ) P ) work. Give every pending job a sufficiently large multiple of C ∗ α − 2 A ( n ) P C_{*}\alpha^{-2}A(n)\mathcal{P} C ∗ α − 2 A ( n ) P work per affected tick. Each large level then finishes within
b ≤ α 2 m 64 C ∗ (11) b \le\frac{\alpha^{2}m}{64C_{*}} \tag*{(11)} b ≤ 64 C ∗ α 2 m (11)
ticks. The fixed cutoff absorbs setup costs and rounding.
Lemma C.2 (Late opening meets every deadline). Every job completes a contracting chain by its deadline. A center born on m m m points is at most α m / C ∗ \alpha m/C_{*} α m / C ∗ ticks old when activated, and one job opens at most one large level in any tick.
Proof. At a first gate crossing, the residual changes size by at most one, and the remaining time decreases by one. Hence
α m / C ∗ − 2 < r ≤ α m / C ∗ . \alpha m/C_{*} - 2 < r \le\alpha m/C_{*}. α m / C ∗ − 2 < r ≤ α m / C ∗ . The explicitly checked core and the age bound give child size m ′ ≤ ( 1 − α / 4 ) ( m + b ) m' \le(1-\alpha/4)(m+b) m ′ ≤ ( 1 − α /4 ) ( m + b ) at completion. Therefore
( r − b ) − α m ′ / C ∗ > α 2 m 4 C ∗ − b ( 1 + α / C ∗ ) − 2 > 0. (r-b)-\alpha m'/C_{*} > \frac{\alpha^{2}m}{4C_{*}}-b(1+\alpha/C_{*})-2>0. ( r − b ) − α m ′ / C ∗ > 4 C ∗ α 2 m − b ( 1 + α / C ∗ ) − 2 > 0. by (10)–(11). The child’s gate is still closed; its later opening is another first crossing. This proves the invariant inductively and prevents two large openings in one tick. Each completed prefix contracts by 1 − α / 4 1-\alpha/4 1 − α /4 , so its depth is O ( α − 1 log n ) O(\alpha^{-1}\log n) O ( α − 1 log n ) . At the deadline the gate must hold, and the first-crossing inequality rules out a large unopened residual. The terminal leaf has size at most 3 L + 2 3L+2 3 L + 2 . Every center’s age is bounded by the number of root ticks remaining when it was opened, proving the activation-age assertion.
The serving chain changes each shared root membership tree only once. A pending job then updates its own radius dictionary and lower pools, without applying that root membership change again. An ancestor replacement supersedes completed descendant jobs; surviving ancestor jobs are unaffected by replacement of a descendant. The new root takes ownership of the shared input pool. Newly installed nodes retain their true age, counted conservatively by elapsed job-root ticks. Refreshing all installed caches costs only a polynomial factor because the chain has polynomial depth. Every affected surviving cache is refreshed before an answer is exposed, so a deleted identity cannot remain in a published pair. A leaf growing to 6 L + 1 6L+1 6 L + 1 is rebuilt immediately within the polynomial leaf budget.
Only D 0 = O ( α − 1 log n ) D_{0}=O(\alpha^{-1}\log n) D 0 = O ( α − 1 log n ) serving nodes own jobs, each with at most D 0 D_{0} D 0 pending levels. Their retained birth cardinalities sum to n poly ( d , log n ) n\operatorname{poly}(d,\log n) n poly ( d , log n ) , including local frozen generations. Since m 1 + σ ≤ n σ m m^{1+\sigma}\le n^{\sigma}m m 1 + σ ≤ n σ m , total space is n 1 + σ P n^{1+\sigma}\mathcal{P} n 1 + σ P . Persistent trees and owned index records have bounded outdegree. Retire roots onto a queue and spend a fixed multiple of allocation work reclaiming unreachable records. Reference counts or ownership arenas make each retired record cost constant work plus its outgoing references. This prevents an activation from synchronously freeing a large index. Queued records are bounded by the simultaneously live generations and one additional construction’s allocation budget; their storage is included in the preceding bound.
Algorithm 4 One external update and its cached diameter answer
Input: Current serving chain, its replacement jobs, and a valid point update.
Apply the update to the serving pools, radius dictionaries, and local matchings.
for each affected serving node’s pending replacement job do
Route the same point change through its completed prefix.
Advance its root clock and perform its prescribed construction budget.
Open its residual level only when the late-opening gate holds.
end for
Install completed jobs from highest root to lowest; cancel obsolete descendant jobs.
Preserve each installed center’s birth size and true age.
Start due serving-node replacement jobs; handle polynomial-size leaves exactly.
Refresh affected baseline pairs and the maximum cached local matching witnesses.
Perform the scheduled retirement work.
return the largest current cached pair, including the exact leaf’s pair; use the distinct-identity convention when its length is zero.
Zero error on an unbounded adaptive stream
For expected amortized time, replace the late-opening schedule by synchronous reconstruction at the same constant-fraction age threshold. Use the certified center constructor and certified angular indices. The cores are verified, all answers are checked, and every unsuccessful construction is retried. Rebuilding a suffix born on M M M points costs M A ( n ) P M A(n)P M A ( n ) P in conditional expectation. Its Ω ( α M ) \Omega(\alpha M) Ω ( α M ) preceding changes pay for that work; the sum of sizes in its contracting chain is O ( M / α ) O(M/\alpha) O ( M / α ) . Charging whole suffixes, rather than separately charging descendants canceled early by an ancestor, gives total birth cardinality t poly ( d , log n ) t\operatorname{poly}(d,\log n) t poly ( d , log n ) over t t t updates. Fresh constructors have their bounds conditionally on the entire history at birth. More explicitly, charge a triggered suffix to the old root’s age-counter updates since its birth. One past external update can be charged only by nodes on its then-current chain, at most O ( α − 1 log n ) O(\alpha^{-1}\log n) O ( α − 1 log n ) times. A descendant canceled before its own trigger incurs no separate charge: its construction was included in its ancestor’s suffix build.
The remaining issue is the cost of adaptive queries to exposed seeds. A bound for each query fixed before the random choices does not alone control an adversary that sees those choices and then selects a slow query. We need a single event on which every direction is fast in at least one certified copy. On its complement, exact scans preserve correctness and the finite lifetime of the generation bounds the total extra work.
The following is the interface provided by the certified search lemmas. For each direction z z z in a fixed implicit net, there is a birth-random variable Z z Z_z Z z of expectation at most A ( n ) P A(n)P A ( n ) P that deterministically bounds the search work for every later subset, every compatible exact predicate, and every accepted inverse phase. The variable counts query labels and rejected incidences against the whole birth pool . It is independent of the later choice of subset. The net is fixed before the family’s fresh coins; it is used only in the analysis.
Lemma C.3 (Adaptive certified generation compiler). Under this birth-variable interface, certified search has always-correct expected total work t A ( n ) poly ( d , B , log n ) tA(n)\operatorname{poly}(d,B,\log n) t A ( n ) poly ( d , B , log n ) over every fixed finite adaptive prefix of t t t external updates. It needs no prescribed horizon.
Proof. Race r r r independent complete certified copies for a large constant multiple of A ( n ) P A(n)P A ( n ) P work each. Use the first completed answer; if none finishes, scan the current pool exactly. Certification makes both answers correct. For a fixed net point, Markov’s inequality bounds the chance that one copy is slow by 1 / 4 1/4 1/4 . Independence and a union bound give probability at most ∣ N ∣ − 4 r |\mathcal{N}|^{-4r} ∣ N ∣ − 4 r that any direction has no fast copy. A padded net comparison covers every actual query. Take r = O ( log ∣ N ∣ + log ( 1 / ε ∗ ) ) r = O(\log|\mathcal{N}| + \log(1/\varepsilon_*)) r = O ( log ∣ N ∣ + log ( 1/ ε ∗ )) .
A node born on M M M points causes at most C 0 M C_0M C 0 M primitive queries and generation births before replacement, where C 0 C_0 C 0 is polynomial in the displayed parameters. Even if a bad generation is deliberately exploited, it causes at most C 0 2 M 2 C_0^2M^2 C 0 2 M 2 exact-scan work during that node’s lifetime, after enlarging C 0 C_0 C 0 . Choose ε ∗ = ( 100 C 0 3 ( n + 1 ) 4 ) − 1 \varepsilon_* = (100C_0^3(n+1)^4)^{-1} ε ∗ = ( 100 C 0 3 ( n + 1 ) 4 ) − 1 . Summing over at most C 0 M C_0M C 0 M births gives expected fallback work O ( M P ) O(MP) O ( M P ) for that node. At each birth, condition on the preceding history; its existence and birth pool are already fixed, while its new complete copies are independent. The tower property therefore justifies this sum even when earlier bad seeds affect later births.
Charge the resulting lifetime bounds to the total birth cardinality proved above. Conditional expected bounds for inverse reconstruction and certified center retries are charged in the same way. No step uses a stopping-time claim about an already exposed seed, and no failure budget is spent over the age of the stream. All retries terminate almost surely; all work areas obey their deterministic space caps.
A single algorithm with a vanishing exponent allowance
The fixed-allowance theorem can be made uniform in the capacity without changing the polynomial degree in dimension. A separate algorithm for each fixed allowance η > 0 \eta> 0 η > 0 does not by itself give one algorithm with allowance tending to zero: its constants, dimension exponent, or validity cutoff could depend uncontrollably on n n n . We therefore revisit the explicit cover construction, choose all margins as computable functions of n n n , and bound every resulting cost with one fixed polynomial degree. The proof spends the shrinking allowance in running time while keeping the space exponent exactly 1 + σ 1+\sigma 1 + σ .
Theorem D.1 (Quantified subpolynomial overhead). Fix 1 < c < 2 1 < c < \sqrt{2} 1 < c < 2 and 0 ≤ σ ≤ 2 / c 2 − 1 0 \le\sigma\le2/c^2 - 1 0 ≤ σ ≤ 2/ c 2 − 1 . Assume these constants are rational, or can be approximated to k k k bits with certified error in poly ( k ) \operatorname{poly}(k) poly ( k ) time. There is one finite-word zero-error dynamic diameter algorithm with all-time space
n 1 + σ poly c , σ ( d , B , log ( 2 n ) ) n^{1+\sigma}\operatorname{poly}_{c,\sigma}(d,B,\log(2n)) n 1 + σ poly c , σ ( d , B , log ( 2 n )) and expected amortized update time
n Λ c ( σ ) + O c , σ ( ( log ( 2 n ) ) − 1 / 100 ) poly c , σ ( d , B , log ( 2 n ) ) . (12) n^{\Lambda_c(\sigma)+O_{c,\sigma}((\log(2n))^{-1/100})}\operatorname{poly}_{c,\sigma}(d,B,\log(2n)). \tag*{(12)} n Λ c ( σ ) + O c , σ (( l o g ( 2 n ) ) − 1/100 ) poly c , σ ( d , B , log ( 2 n )) . (12) The polynomial degrees are independent of n n n and of the shrinking allowance. The algorithm is always correct on an unbounded, exposed-seed adaptive stream and needs no update horizon.
The capped, scheduled version has the same power of n n n , worst-case update time, and all-time space, with poly c , σ ( d , B , log ( 2 n t / δ ) ) \operatorname{poly}_{c,\sigma}(d,B,\log(2nt/\delta)) poly c , σ ( d , B , log ( 2 n t / δ )) factors, and simultaneous correctness probability 1 − δ 1-\delta 1 − δ over t t t adaptive updates. Thus both variants may be written with exponent Λ c ( σ ) + o ( 1 ) \Lambda_c(\sigma)+o(1) Λ c ( σ ) + o ( 1 ) , while retaining the exact space exponent 1 + σ 1+\sigma 1 + σ .
Proof. We specify all parameters that were previously held fixed. Write
L = max { 2 , log ( 2 n ) } , ζ = 1 / 100. L = \max\{2,\log(2n)\}, \qquad\zeta= 1/100. L = max { 2 , log ( 2 n )} , ζ = 1/100.
Constants below may depend on c , σ c,\sigma c , σ , but not on n n n , the input dimension, or coordinate precision. Bounded n n n below a fixed ( c , σ ) (c,\sigma) ( c , σ ) -dependent cutoff can be handled exactly.
Geometry and the birth-size cutoff. Choose all radial, local-scale, original-query-net, and padding reserves as conservative rationals of order L − ζ L^{-\zeta} L − ζ . The local matching inequalities then hold with approximation at most c c c , and the common angular problem has
h n = g c − O c ( L − ζ ) , δ n = Θ c ( L − ζ ) , g c = c 2 − 1. h_n = g_c - O_c(L^{-\zeta}), \qquad\delta_n = \Theta_c(L^{-\zeta}), \qquad g_c = c^2 - 1. h n = g c − O c ( L − ζ ) , δ n = Θ c ( L − ζ ) , g c = c 2 − 1.
Here h n h_n h n is the strong correlation and − δ n -\delta_n − δ n bounds rejected correlations. Above a fixed cutoff, g c / 2 ≤ h n < g c < 1 g_c/2 \le h_n < g_c < 1 g c /2 ≤ h n < g c < 1 . The number of local configurations and the reciprocal net precision are polynomial in L L L , with fixed degrees.
A generation with birth size
m < exp ( L ) m < \exp(\sqrt{L}) m < exp ( L )
uses exact scanning instead of filters. Its space is linear in its birth records, deletion is immediate, and query work is n O ( L − 1 / 2 ) poly ( d , B ) n^{O(L^{-1/2})}\operatorname{poly}(d,B) n O ( L − 1/2 ) poly ( d , B ) . For fixed c < 2 c < \sqrt{2} c < 2 , Λ c ( σ ) > 0 \Lambda_c(\sigma) > 0 Λ c ( σ ) > 0 , so this fits (12) above a fixed cutoff. As in the finite-word construction, a generation whose original ambient dimension is at least m m m may also be scanned: O ( m d ) ≤ O ( d 2 ) O(md) \le O(d^2) O ( m d ) ≤ O ( d 2 ) . Hence it remains to treat
ℓ = log m ≥ L , d < m . \ell= \log m \ge\sqrt{L}, \qquad d < m. ℓ = log m ≥ L , d < m .
The finite family with explicit shrinking margins. Use a moderate block dimension
B m o d = Θ c ( L 2 ζ ℓ ) , B_{\mathrm{mod}} = \Theta_c(L^{2\zeta}\ell), B mod = Θ c ( L 2 ζ ℓ ) ,
rounded up to a power of four. Spherical concentration with distortion at most δ n / 16 \delta_n/16 δ n /16 then makes every rejected birth pair nonpositive in every normalized outer block, for a fixed query, except with probability at most m − 30 m^{-30} m − 30 . This is the only dependence on the negative margin in the projection dimension. Pad to a power-of-four ambient dimension D = O ( d + B m o d ) D = O(d+B_{\mathrm{mod}}) D = O ( d + B mod ) . For the large birth sizes under consideration, B m o d < m B_{\mathrm{mod}} < m B mod < m ; thus D = O ( m ) D = O(m) D = O ( m ) when d < m d < m d < m , and the same polynomial-size union bound as before applies.
Take b = Θ ( ℓ 2 / 3 ) b = \Theta(\ell^{2/3}) b = Θ ( ℓ 2/3 ) , also a power of four, and s = B m o d / b s = B_{\mathrm{mod}}/b s = B mod / b . The exact splitter family S s p l i t S_{\mathrm{split}} S split has
log ∣ S s p l i t ∣ = O ( s log B m o d ) , s = O c ( L 2 ζ ℓ 1 / 3 ) , ϵ s p l i t = O ( ℓ − 1 / 3 ) . \log|S_{\mathrm{split}}| = O(s \log B_{\mathrm{mod}}), \qquad s = O_c(L^{2\zeta}\ell^{1/3}), \qquad\epsilon_{\mathrm{split}} = O(\ell^{-1/3}). log ∣ S split ∣ = O ( s log B mod ) , s = O c ( L 2 ζ ℓ 1/3 ) , ϵ split = O ( ℓ − 1/3 ) .
The three-vector splitting proof and its rational representation do not change. In particular, the target correlation in a small block is at least h n − 2 ϵ s p l i t h_n - 2\epsilon_{\mathrm{split}} h n − 2 ϵ split .
Choose rational angular and space parameters within O c , σ ( L − ζ ) O_{c,\sigma}(L^{-\zeta}) O c , σ ( L − ζ ) of the minimizing parameters in § 6.5 , rounding the internal space parameter downward. Let u u u , q q q , κ \kappa κ be the resulting values. They can be chosen so that κ ∈ [ 1 / 2 , 1 ] \kappa\in[1/2,1] κ ∈ [ 1/2 , 1 ] and
max { b e x p + 3 v , f e x p + 2 v } ≤ Λ c ( σ ) + O c , σ ( L − ζ ) , \max\{b_{\mathrm{exp}} + 3v,\ f_{\mathrm{exp}} + 2v\} \le\Lambda_c(\sigma) + O_{c,\sigma}(L^{-\zeta}), max { b exp + 3 v , f exp + 2 v } ≤ Λ c ( σ ) + O c , σ ( L − ζ ) ,
where
a = κ u , b e x p = κ q , f e x p = 1 + κ ( q − 1 ) , v = ( a − σ i n t ) + , σ i n t ≤ σ . a = \kappa u,\qquad b_{\mathrm{exp}} = \kappa q,\qquad f_{\mathrm{exp}} = 1 + \kappa(q - 1),\qquad v = (a-\sigma_{\mathrm{int}})_+,\qquad\sigma_{\mathrm{int}} \le\sigma. a = κ u , b exp = κ q , f exp = 1 + κ ( q − 1 ) , v = ( a − σ int ) + , σ int ≤ σ .
The corresponding construction and deletion exponents satisfy the same bound, by the maintenance inequalities already proved. The rational choices have polynomial encoding length in log n \log n log n .
Define the local Gaussian threshold by t 2 = 2 κ ℓ + O ( 1 ) t^2 = 2\kappa\ell+ O(1) t 2 = 2 κ ℓ + O ( 1 ) , and its small-block threshold by t 0 = t / s t_0 = t/\sqrt{s} t 0 = t / s . Uniformly for ℓ ≥ L \ell\ge\sqrt{L} ℓ ≥ L ,
t 0 2 = Ω c ( ℓ 2 / 3 L − 2 ζ ) = Ω c ( L 1 / 3 − 2 ζ ) ⟶ ∞ . t_0^2 = \Omega_c(\ell^{2/3}L^{-2\zeta}) = \Omega_c(L^{1/3-2\zeta}) \longrightarrow\infty. t 0 2 = Ω c ( ℓ 2/3 L − 2 ζ ) = Ω c ( L 1/3 − 2 ζ ) ⟶ ∞.
All small-sphere tail estimates therefore apply. The good-pair Gaussian constant is uniform: h n h_n h n lies in a fixed compact interval inside ( 0 , 1 ) (0,1) ( 0 , 1 ) , and h n ≤ x ≤ 1 h_n \le x \le1 h n ≤ x ≤ 1 . The small-block target h n − 2 ϵ s p l i t h_n-2\epsilon_{\mathrm{split}} h n − 2 ϵ split and the checked net threshold h n − 3 ϵ s p l i t h_n-3\epsilon_{\mathrm{split}} h n − 3 ϵ split lie in such a compact interval as well, so the same uniform rectangle estimate applies to the actual certificate. In particular, the explicit constant 2 − ⌈ 100 / ( 1 − h n ) ⌉ 2^{-\lceil100/(1-h_n)\rceil} 2 − ⌈ 100/ ( 1 − h n )⌉ is bounded below by a positive constant depending only on c c c ; it contains no exponential dependence on 1 / δ n 1/\delta_n 1/ δ n .
Use the same small-sphere net of radius b − 2 b^{-2} b − 2 , norm cutoff G = O ( ℓ ) G=O(\sqrt{\ell}) G = O ( ℓ ) , and exact cover certificate. The inequality needed for the net margin holds uniformly, since
G b − 2 t 0 = O c ( ℓ − 1 / 2 L − ζ ) = o ( 1 ) . G b^{-2}t_0 = O_c(\ell^{-1/2}L^{-\zeta})=o(1). G b − 2 t 0 = O c ( ℓ − 1/2 L − ζ ) = o ( 1 ) .
The base-family size M b a s e M_{\mathrm{base}} M base satisfies
log M b a s e = I h n ( x ) t 2 2 s + O c ( ϵ s p l i t t 2 s + log L ) . \log M_{\mathrm{base}}=I_{h_n}(x)\frac{t^2}{2s} + O_c\left(\epsilon_{\mathrm{split}}\frac{t^2}{s}+\log L\right). log M base = I h n ( x ) 2 s t 2 + O c ( ϵ split s t 2 + log L ) .
The net-verification logarithm is O ( b log b ) O(b\log b) O ( b log b ) . Consequently the logarithm of the entire implicit description, or its expected certification work, apart from a fixed polynomial factor in D , B D,B D , B , is at most
O c ( L 2 ζ ℓ 1 / 3 log L + ℓ 2 / 3 log L ) . O_c\left(L^{2\zeta}\ell^{1/3}\log L+\ell^{2/3}\log L\right). O c ( L 2 ζ ℓ 1/3 log L + ℓ 2/3 log L ) .
Dividing by ℓ ≥ L \ell\ge\sqrt{L} ℓ ≥ L gives
O c ( L 2 ζ − 1 / 3 log L + L − 1 / 6 log L ) = o ( L − ζ ) . (13) O_c\left(L^{2\zeta-1/3}\log L+L^{-1/6}\log L\right)=o(L^{-\zeta}). \tag*{(13)} O c ( L 2 ζ − 1/3 log L + L − 1/6 log L ) = o ( L − ζ ) . (13)
This explicitly controls description size, finite-net enumeration, and the expected resampling work.
The full raw-universe logarithm has the leading term κ I h n ( x ) ℓ \kappa I_{h_n}(x)\ell κ I h n ( x ) ℓ . Its remaining terms come from splitter count, cover prefactors, the 2 s 2^s 2 s conditioning loss, and the norm-gate error. After division by ℓ \ell ℓ , their sum is
O c ( ℓ − 1 / 3 + L 2 ζ ℓ − 2 / 3 log L ) = o ( L − ζ ) . O_c\left(\ell^{-1/3}+L^{2\zeta}\ell^{-2/3}\log L\right)=o(L^{-\zeta}). O c ( ℓ − 1/3 + L 2 ζ ℓ − 2/3 log L ) = o ( L − ζ ) .
Exactly the same bound applies to the data, query, and pair moment exponents. The bad-pair sum still contains the actual m m m birth points. All finite Gaussian and rotation exceptions retain their m − 30 m^{-30} m − 30 or smaller budgets. Their deterministic full-enumeration bound remains polynomial in m , D , B m,D,B m , D , B , so they add no larger term. No error budget is changed to use m κ m^\kappa m κ .
Exact space and fixed polynomial degrees. Choose a computable rational
η n = C c , σ L − ζ \eta_n=C_{c,\sigma}L^{-\zeta} η n = C c , σ L − ζ
within constant factors of this value, with the constant large enough to dominate the preceding explicit losses. Above a fixed cutoff it is less than 1 / 100 1/100 1/100 . Point assignment gives
R ≤ m a + η n P , U ≤ m κ ( 1 + u ) + η n P , U ≤ m R , R\le m^{a+\eta_n}\mathcal{P},\qquad U\le m^{\kappa(1+u)+\eta_n}\mathcal{P},\qquad U\le mR, R ≤ m a + η n P , U ≤ m κ ( 1 + u ) + η n P , U ≤ m R ,
after setting R ≥ ⌈ U / m ⌉ R\ge\lceil U/m\rceil R ≥ ⌈ U / m ⌉ as before. The implicit rank oracle costs m η n P m^{\eta_n}\mathcal{P} m η n P . Use a power-of-two inverse parameter within a factor of two of m v + 2 η n m^{v+2\eta_n} m v + 2 η n , excluding the polynomial dimension factor. The native condition 3 v + 6 η n < 1 + a 3v+6\eta_n<1+a 3 v + 6 η n < 1 + a holds uniformly above a fixed cutoff: on the first branch a , v a,v a , v remain near the bounded optimizer, and on the second branch v = 0 v=0 v = 0 . The inverse and its low-workspace verifier use
O ~ ( m R / m v + 2 η n ) ≤ m 1 + σ i n t − η n P ≤ m 1 + σ P . \widetilde{O}\left(mR/m^{v+2\eta_n}\right)\le m^{1+\sigma_{\mathrm{int}}-\eta_n}\mathcal{P}\le m^{1+\sigma}\mathcal{P}. O ( m R / m v + 2 η n ) ≤ m 1 + σ int − η n P ≤ m 1 + σ P .
Original point records and the global family description also fit. Thus the shrinking allowance is spent only in time, not in space.
Here and in these estimates P \mathcal{P} P has a degree independent of n n n . To see this directly, the outer matrices have dimension O ( d + L 1 + 2 ζ ) O(d+L^{1+2\zeta}) O ( d + L 1 + 2 ζ ) ; their exact rational construction and application use a fixed polynomial number of operations. Splitter enumeration and net verification are already accounted for in (13) , rather than hidden in the dimension polynomial. Rank selection uses integer products and base-cap scans. Every geometric comparison has degree at most thirty-two and polynomial coefficient length. Required coupling precision is polynomial in log m \log m log m , log D \log D log D , log ( 1 / δ n ) \log(1/\delta_n) log ( 1/ δ n ) , hence in d d d , B B B , log n \log n log n with fixed degrees. The rational center LPs, verified inverse routines, and balanced dictionaries likewise have fixed polynomial degrees. There is no operation of the form d 1 / η n d^{1/\eta_n} d 1/ η n , and no uncontrolled constant of the form exp ( 1 / δ n ) \exp(1/\delta_n) exp ( 1/ δ n ) .
All earlier large-size requirements have now been checked by explicit powers of L L L and ℓ \ell ℓ : b ≤ B m o d b \le B_{\mathrm{mod}} b ≤ B mod , ϵ s p l i t < h n / 10 \epsilon_{\mathrm{split}} < h_n/10 ϵ split < h n /10 , t 0 ≥ 1 t_0 \ge1 t 0 ≥ 1 , and G b − 2 t 0 = o ( 1 ) G b^{-2t_0}=o(1) G b − 2 t 0 = o ( 1 ) . Thus the remaining cutoff is one fixed number depending on c , σ c,\sigma c , σ , not an unspecified cutoff depending on the current value of η n \eta_n η n .
Dynamic composition. The scaled resource proposition gives initialization m A ( n ) mA(n) m A ( n ) , original-point maintenance A ( n ) A(n) A ( n ) , and a birth-envelope query bound of expectation at most A ( n ) A(n) A ( n ) , where
A ( n ) = n Λ c ( σ ) + O c , σ ( L − ζ ) poly c , σ ( d , B , L ) . A(n)=n^{\Lambda_c(\sigma)+O_{c,\sigma}(L^{-\zeta})}\operatorname{poly}_{c,\sigma}(d,B,L). A ( n ) = n Λ c ( σ ) + O c , σ ( L − ζ ) poly c , σ ( d , B , L ) .
Small scanned generations satisfy the same interface. The number of local configurations, query-net amplification copies, and lifetime factors has increased only polynomially in L L L . Apply Lemma C.3 to obtain the zero-error theorem, including unbounded adaptivity and all-time exact space. Applying instead the capped phase and frozen-generation schedules of Section C.1 yields the stated worst-case Monte Carlo version. Its extra horizon and confidence factors are polynomial logarithmic and do not enter the power of n n n .
This statement concerns fixed c , σ c,\sigma c , σ . It does not claim polynomial dependence on 1 / ( c − 1 ) 1/(c-1) 1/ ( c − 1 ) uniformly as c c c tends to one, or polynomial dependence on the reciprocal of an arbitrarily prescribed exponent allowance.
A static farthest-neighbor consequence
The same geometric reduction gives a static search structure with near-linear preprocessing and space. We first retain a lifted-center chain and an all-query baseline at each node. An asymmetric choice of the explicit angular filters then makes their data cost near-linear while retaining the desired query exponent. Finally, amplification over direction nets makes the guarantee simultaneous for every query, including a query chosen after the structure’s seeds have been revealed. The Monte Carlo construction uses explicit filters; the zero-error variant below uses certified inverses to keep its exact space exponent.
Corollary E.1 (Static farthest-neighbor search). Fix 1 < c < 2 1<c<\sqrt{2} 1 < c < 2 and 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 . A nonempty set of n n n points in R d \mathbb{R}^d R d admits a Monte Carlo farthest-neighbor structure with worst-case preprocessing time and all-outcome space
n 1 + o ( 1 ) poly c ( d , log ( 2 n / δ ) ) , n^{1+o(1)}\operatorname{poly}_c(d,\log(2n/\delta)), n 1 + o ( 1 ) poly c ( d , log ( 2 n / δ )) , and worst-case query time
n c 2 ( 2 − c 2 ) + o ( 1 ) poly c ( d , log ( 2 n / δ ) ) . n^{c^2(2-c^2)+o(1)}\operatorname{poly}_c(d,\log(2n/\delta)). n c 2 ( 2 − c 2 ) + o ( 1 ) poly c ( d , log ( 2 n / δ )) .
With probability at least 1 − δ 1-\delta 1 − δ , it returns an actual c c c -approximate farthest point for every query, including queries chosen after the entire structure and its seeds are exposed. The o ( 1 ) o(1) o ( 1 ) terms can be taken as O c ( log log ( 4 n ) / log ( 2 n ) ) O_c(\log\log(4n)/\sqrt{\log(2n)}) O c ( log log ( 4 n ) / log ( 2 n ) ) and do not depend on d d d . The arithmetic-RAM statement holds for arbitrary real inputs. Rational data and queries of encoding length at most B B B have ordinary running-time bounds with an additional fixed polynomial factor in B B B .
Proof. An empty set reports None, and a singleton returns its sole point. For all bounded n n n below a fixed c c c -dependent cutoff, scan exactly; this also covers the constant adjustments ensuring t ≥ 1 t \ge1 t ≥ 1 . Let L = log ( 2 n ) L=\log(2n) L = log ( 2 n ) . Build the static lifted-center chain from § 5 , using the Monte Carlo constructor and checking that each core has size at least α m / 2 \alpha m/2 α m /2 . On an unsuccessful core check use the same deterministic contraction fallback as in the dynamic construction. This caps the depth and total input cardinality on every outcome. A polynomial-size exact leaf ends the chain. The rational implementation uses the sampled centerpoint program; no strongly polynomial real linear-programming assumption is needed.
At each node take one fresh halfspace α \alpha α -net of its lifted fixed input pool. Its size is
O ( α − 1 ( ( d + 2 ) log ( 1 / α ) + log ( n / δ ) ) ) O\left(\alpha^{-1}\left((d+2)\log(1/\alpha)+\log(n/\delta)\right)\right) O ( α − 1 ( ( d + 2 ) log ( 1/ α ) + log ( n / δ ) ) )
after increasing the constant for the polynomial number of nodes. The halfspace-net theorem [22 ] , conditional on the center, shows that this one sample hits every witness halfspace in Lemma 5.1 simultaneously. Thus, for every q q q , scanning the stored sample returns an actual distance L q L_q L q with
L q 2 ≥ V + Q 2 , Q = ∥ q − o ∥ . (14) L_q^2 \ge V+Q^2,\qquad Q=\lVert q-o\rVert. \tag*{(14)} L q 2 ≥ V + Q 2 , Q = ∥ q − o ∥ . (14)
Center and net failures receive conditional budgets whose sum is at most δ / 2 \delta/2 δ /2 . All random sampling has a deterministic work cap; a failed cap is included in this budget. Alternatively, on rational inputs a checked disjoint block gives the same all-query baseline, with expected linear preprocessing per node.
Choose the local parameters of § 9 with ϵ = Θ c ( 1 / L ) \epsilon=\Theta_c(1/L) ϵ = Θ c ( 1/ L ) . At a node with V > 0 V>0 V > 0 , store its core points in their inward radial shells. Build the angular index for each eligible left-shell, right-shell, and weak-scale configuration from (4) ; its data pool is the whole corresponding core shell. The right shell now describes a query radius, not a second stored point set. On query q q q , obtain L q L_q L q . If V = 0 V=0 V = 0 or Q > K V Q>K\sqrt{V} Q > K V , the baseline covers the core within factor c c c . Otherwise round Q Q Q inward on the same grid, and query the configurations for that right shell and scales R ℓ > L q R_\ell>L_q R ℓ > L q . A zero right shell makes no angular calls; its core distances are already covered by the baseline. Accept exactly the original angular weak predicate, and measure each returned point’s actual distance from q q q . Take the maximum of all such distances, all node baselines, and an exact leaf scan.
Here is the local approximation proof. Let D C = max p ∈ C ∥ p − q ∥ D_C=\max_{p\in C}\lVert p-q\rVert D C = max p ∈ C ∥ p − q ∥ . If D C ≤ c L q D_C\le cL_q D C ≤ c L q , the baseline suffices. Otherwise V > 0 V>0 V > 0 , Q ≤ K V Q\le K\sqrt{V} Q ≤ K V , and the geometric scale grid contains R ℓ R_\ell R ℓ such that
L q < R ℓ < D C / κ , R ℓ ≥ D C / ( κ λ ) > D C / c . L_q<R_\ell<D_C/\kappa,\qquad R_\ell\ge D_C/(\kappa\lambda)>D_C/c. L q < R ℓ < D C / κ , R ℓ ≥ D C / ( κλ ) > D C / c .
Rounding the target and query loses at most 2 ϵ V < 2 ϵ R ℓ 2\epsilon\sqrt{V}<2\epsilon R_\ell 2 ϵ V < 2 ϵ R ℓ , leaving a strong rounded pair. Its squared shell radii sum to at most V + Q 2 ≤ L q 2 < R ℓ 2 V+Q^2\le L_q^2<R_\ell^2 V + Q 2 ≤ L q 2 < R ℓ 2 , so its configuration is eligible. Neither rounded radius is zero in this case. A successful angular query returns a weak rounded pair. Joint convexity gives
∥ p ~ − q ~ ∥ ≤ max { ∥ p − q ∥ , ∥ p − o ∥ , Q } ≤ max { ∥ p − q ∥ , L q } . \lVert\tilde p-\tilde q\rVert\le\max\{\lVert p-q\rVert,\lVert p-o\rVert,Q\}\le\max\{\lVert p-q\rVert,L_q\}. ∥ p ~ − q ~ ∥ ≤ max {∥ p − q ∥ , ∥ p − o ∥ , Q } ≤ max {∥ p − q ∥ , L q } .
Its actual distance is therefore greater than R ℓ > D C / c R_\ell>D_C/c R ℓ > D C / c . Every data point belongs to a core or the leaf, proving the global farthest-neighbor guarantee. Zero shell directions need not be indexed; the same baseline covers them.
It remains to obtain near-linear preprocessing at the endpoint u = 0 u=0 u = 0 . Use the common lifted correlation h = c 2 − 1 − O c ( 1 / L ) h=c^2-1-O_c(1/L) h = c 2 − 1 − O c ( 1/ L ) and set x = h x=h x = h . For every nonempty shell index use the same global tensor parameters
ℓ = ⌈ L ⌉ , L ≤ ℓ t 2 / 2 ≤ L + O ( 1 ) , t ≥ 1. \ell=\lceil\sqrt{L}\rceil,\qquad L\le\ell t^2/2\le L+O(1),\qquad t\ge1. ℓ = ⌈ L ⌉ , L ≤ ℓ t 2 /2 ≤ L + O ( 1 ) , t ≥ 1.
The good-cap exponent is exactly I h ( h ) = 1 I_h(h)=1 I h ( h ) = 1 . Hence the explicit construction of Lemma 6.3 has
log A = L + O c ( L log L ) , E u = exp ( O c ( L log L ) ) , E q = n 1 − h 2 exp ( O c ( L log L ) ) . \log A=L+O_c(\sqrt{L}\log L),\qquad E_u=\exp(O_c(\sqrt{L}\log L)),\qquad E_q=n^{1-h^2}\exp(O_c(\sqrt{L}\log L)). log A = L + O c ( L log L ) , E u = exp ( O c ( L log L )) , E q = n 1 − h 2 exp ( O c ( L log L )) .
Base-list evaluation also costs exp ( O c ( L log L ) ) \exp(O_c(\sqrt{L}\log L)) exp ( O c ( L log L )) . Each pool has at most n n n points, so the whole-birth bad-occurrence bound uses n A p ℓ 2 ≤ E q nAp_\ell^2\le E_q n A p ℓ 2 ≤ E q , regardless of that pool’s size. Empty indices return none immediately. Thus small birth pools require no separate asymptotic cutoff.
Amplify the capped explicit indices over the original-direction net, all birth targets, and the polynomial number of configurations, with remaining failure budget δ / 2 \delta/2 δ /2 . The union bound is over this fixed finite family and its direction nets, rather than over a sequence of queries. The padded-net guarantee then gives one event valid for every later query, so no query horizon is needed. The total stored core memberships and node inputs are n poly ( d , log ( n / δ ) ) n\operatorname{poly}(d,\log(n/\delta)) n poly ( d , log ( n / δ )) , so the displayed preprocessing and space bounds follow. The query visits only polynomially many logarithmic levels and configurations. Finally, 1 − h 2 = c 2 ( 2 − c 2 ) + O c ( 1 / L ) 1-h^2=c^2(2-c^2)+O_c(1/L) 1 − h 2 = c 2 ( 2 − c 2 ) + O c ( 1/ L ) , whose extra factor in time is constant. Tensor depth affects the logarithmic overhead, never a power of the ambient dimension. Finite Gaussian coupling and exact signed comparisons are as in the explicit dynamic structure.
For binary points and c = 2 − θ c=\sqrt{2-\theta} c = 2 − θ , the corollary gives Hamming ( 2 − θ ) (2-\theta) ( 2 − θ ) -FNS query exponent 2 θ − θ 2 + o ( 1 ) 2\theta-\theta^2+o(1) 2 θ − θ 2 + o ( 1 ) , with n 1 + o ( 1 ) n^{1+o(1)} n 1 + o ( 1 ) preprocessing and space up to polynomial dimension factors. This improves the O ( θ ) O(\sqrt{\theta}) O ( θ ) query exponent for Hamming farthest-neighbor search obtained by Andoni, Jiang, and Zharkov [4 ] . The corollary concerns a fixed data set; the fully dynamic diameter results do not rely on it.
Corollary E.2 (Zero-error static search). For rational inputs and fixed polynomial-time-computable 1 < c < 2 1<c<\sqrt{2} 1 < c < 2 , there is an always-correct static farthest-neighbor structure using n poly c ( d , B , log ( 2 n ) ) n\operatorname{poly}_c(d,B,\log(2n)) n poly c ( d , B , log ( 2 n )) space at all times. For every fixed prefix of t t t queries chosen adaptively after all preceding random choices are exposed, its expected total running time, including preprocessing, is
n 1 + o ( 1 ) poly c ( d , B , log ( 2 n ) ) + t n c 2 ( 2 − c 2 ) + o ( 1 ) poly c ( d , B , log ( 2 n ) ) . n^{1+o(1)}\operatorname{poly}_c(d,B,\log(2n))+tn^{c^2(2-c^2)+o(1)}\operatorname{poly}_c(d,B,\log(2n)). n 1 + o ( 1 ) poly c ( d , B , log ( 2 n )) + t n c 2 ( 2 − c 2 ) + o ( 1 ) poly c ( d , B , log ( 2 n )) . Here B B B bounds data and query encoding lengths. The o ( 1 ) o(1) o ( 1 ) can be taken as O c ( ( log ( 2 n ) ) − 1 / 100 ) O_c((\log(2n))^{-1/100}) O c (( log ( 2 n ) ) − 1/100 ) with fixed polynomial degrees. No query horizon is supplied.
Proof. We retain the certified geometry and refresh only the angular indices. A uniformly fast collection of indices serves every later query within budget. If a query reveals a slower collection, exact scanning answers that query and a fresh independent construction restarts the process. An all-query event is essential here because the query may be chosen after the collection’s seeds are exposed.
Build the static chain with checked disjoint-block certificates. Scanning one fixed block gives (14) for every query by (3) ; it remains intact forever. Keep this geometry unchanged. In each angular pool use Proposition 6.7 with x = h x=h x = h , u = 0 u=0 u = 0 , k = 1 k=1 k = 1 , and σ = ν = 0 \sigma=\nu=0 σ = ν = 0 . Apply the explicit uniform schedule of Appendix § 14 . In this application all raw counts and inverse domains use the actual pool birth size m m m , with the stated small-pool scan cutoff. The resulting complete angular collection has exact linear space up to polynomial factors, expected construction cost B = n 1 + o ( 1 ) P \mathcal{B}=n^{1+o(1)}\mathcal{P} B = n 1 + o ( 1 ) P , and fixed-query birth-envelope expectation at most A = n 1 − h 2 + o ( 1 ) P \mathcal{A} = n^{1-h^2+o(1)}\mathcal{P} A = n 1 − h 2 + o ( 1 ) P . The polynomial P \mathcal{P} P can be enlarged to cover every pool and configuration. As before, h = g c − O c ( ( log n ) − 1 / 100 ) h = g_c - O_c((\log n)^{-1/100}) h = g c − O c (( log n ) − 1/100 ) .
Let J J J be the number of angular pools and configurations. Within each pool, amplify independent complete copies over its original-direction net to failure probability at most 1 / ( 4 J ) 1/(4J) 1/ ( 4 J ) . A union bound gives one event of probability at least 3 / 4 3/4 3/4 on which every pool answers every query within its local race budget. The sum of those budgets is O ( A ) O(\mathcal{A}) O ( A ) after enlarging P \mathcal{P} P . Coverage itself is deterministic. Query the required pools by racing their copies separately. Each completed search is always valid; if any pool’s race exhausts its budget, scan the data exactly, discard all angular indices, and rebuild them with fresh coins before finishing the query. The checked geometry is retained. All attempts obey the same space bound and terminate almost surely.
Let Reach j \operatorname{Reach}_j Reach j denote that the j j j th collection is born. Its occurrence is determined before that collection’s fresh coins. A uniformly fast collection never triggers a rebuild, hence Pr ( Reach j ) ≤ 4 1 − j \Pr(\operatorname{Reach}_j) \le4^{1-j} Pr ( Reach j ) ≤ 4 1 − j , even when queries depend on all previous seeds and construction times. Conditional expected construction cost at every birth is at most B \mathcal{B} B . The tower property therefore bounds all construction work by 4 B / 3 4\mathcal{B}/3 4 B /3 in expectation. Exact fallback scans have the same geometric bound and cost n poly ( d , B ) n\operatorname{poly}(d,\mathcal{B}) n poly ( d , B ) each, absorbed in B \mathcal{B} B . The local races for the first t t t queries cost O ( t A ) O(t\mathcal{A}) O ( t A ) deterministically. This proves the stated expected-prefix bound; it does not assert conditional expected time for an individual query after its structure has been exposed.