For any map \(f:F\to \{ 0,\ldots ,m-1\} \), its \(m\) fibres partition \(F\). One fibre therefore has at most \(\lfloor |F|/m\rfloor \) elements. Apply this to the two coordinate residue maps and choose their residues independently. Each selected strip contains at most \(\lfloor |F|/m\rfloor \) cells, so their union satisfies \(|B_{a,b}(F)|\le 2\lfloor |F|/m\rfloor \). Multiplying by \(m\) and using \(m\lfloor |F|/m\rfloor \le |F|\) gives (2). The argument includes \(F=\varnothing \) and \(m=1\).

Each point of \(T\) contributes an integer square with \((2r+1)^2\) sites; counting their union gives the first bound. Each crossing edge contributes at most two endpoints, giving the second. In each coordinate the remainder modulo two identifies the child label, and division by two then identifies the parent index. Thus distinct parent and child-label pairs give distinct indices, proving the last equality. All three assertions include empty sets.

The floor inequalities give the cell-membership equivalence, and \(\lfloor t/2\rfloor =\lfloor \lfloor t\rfloor /2\rfloor \) gives \(c_{k+1}(x)=p(c_k(x))\). Integer division by \(2\) preserves coordinatewise bounds of the form \(|z_i-w_i|\le C_0\). Finally, every integer \(z_i\) has a unique decomposition \(z_i=2p(z)_i+r_i\) with \(r_i\in \{ 0,1\} \).

Applying \(c_{k+1}(z)=p(c_k(z))\) to \(z\in Z\) gives \(\mathcal Z_{k+1}=p(\mathcal Z_k)\). Because the scale-\(k\) cells partition \(\mathbb R^2\), \(x\in N_k\) if and only if \(c_k(x)\in P_k\). Since \(p\) maps \(P_k\) into \(P_{k+1}\), every point of \(N_k\) has \(c_{k+1}(x)=p(c_k(x))\in P_{k+1}\), so \(N_k\subseteq N_{k+1}\). Finally, \(x\in N_{k+1}\) if and only if \(p(c_k(x))\in P_{k+1}\), that is \(c_k(x)\in \operatorname {Ch}(P_{k+1})\); removing \(N_k\) removes the indices in \(P_k\).

Since \(|\mathcal Z_{k+1}|\le |Z|\), its \(C_0\)-neighborhood \(P_{k+1}\) has at most \((2C_0+1)^2|Z|\) elements, and \(\operatorname {Ch}(P_{k+1})\) has at most \(4|P_{k+1}|\) elements. Each edge in \(\partial _\Lambda A\) contributes at most two endpoints to \(Z\), so \(|Z|\le 2b\).

For any \(z\in Z\) and \(x\in \mathbb R^2\), choosing \(k\ge 0\) with \(2^k{\gt}|x_1-o_1|+|x_2-o_2|+|z_1-o_1|+|z_2-o_2|\) places \((x_i-o_i)/2^k\) and \((z_i-o_i)/2^k\) in \((-1,1)\), so their floors belong to \(\{ -1,0\} \) and \(\| c_k(x)-c_k(z)\| _\infty \le 1\le C_0\). Since \(c_k(z)\in \mathcal Z_k\), it follows that \(c_k(x)\in P_k\) and \(x\in N_k\).

Since \(2^k{\gt}0\), the closure of each half-open coordinate interval is the corresponding closed interval, and closure commutes with finite products and with the finite union \(D_k=\bigcup _{z\in I_k}C_{k,z}\). As a product of closed intervals, \(\overline{C_{k,z}}\) is convex.

The layer \(D_k\) is the union of \(C_{\ell ,w}\) over \(w\in F_{k,\ell }\).

If \(k{\lt}h\), nesting of the neighborhoods gives \(D_k\subseteq N_{k+1}\subseteq N_h\), whereas \(D_h=N_{h+1}\setminus N_h\) is disjoint from \(N_h\). The case \(h{\lt}k\) follows by symmetry.

Nesting gives \(N_{k_0}\subseteq N_k\), and \(D_k=N_{k+1}\setminus N_k\).

Exhaustion of \(\mathbb R^2\) by the neighborhoods \(N_j\) yields a least \(K\ge 0\) with \(x\in N_K\). Since \(x\notin N_{k_0}\) and the neighborhoods \(N_j\) are nested, \(K{\gt}k_0\). Minimality of \(K\) gives \(x\notin N_{K-1}\), so \(x\in D_{K-1}\). Uniqueness follows from pairwise disjointness of the layers.

Every point of \(\mathbb R^2\setminus N_{k_0}\) lies in \(D_k\) for its unique layer index \(k\ge k_0\).

Each coordinate of a closed cell lies in its closed interval of length \(2^k\). Indices differing by at most \(C_0\) therefore give coordinate distances at most \((C_0+1)2^k\). If two integer indices differ by more than \(C_0\), they differ by at least \(C_0+1\); the corresponding closed intervals are separated by at least \(C_0 2^k\). Taking the maximum of the two coordinate distances proves both bounds.

The closure of \(D_k\) is a finite union of closed scale-\(k\) cells. Every layer index lies outside \(P_k\) and so differs from every occupied index in at least one coordinate by more than \(C_0\). Applying the closed-cell lower bound to the cell containing \(z\) gives the first inequality.

Since \(\overline{D_k}\subseteq \overline{N_{k+1}}\), the point \(x\) lies in a closed scale-\((k+1)\) cell whose index is within \(C_0\) of an occupied index. Choosing \(z_*\in Z\) in that occupied cell and applying the closed-cell upper bound at scale \(k+1\) gives the second inequality.

Choose \(z\in Z\) with \(d_\infty (x,z)\le 2(C_0+1)2^k\). Since \(d_\infty (y,z)\ge C_0 2^h\), the triangle inequality gives the first bound. When \(h\ge k+2\), \(4\cdot 2^k\le 2^h\), so

The point lies in a closed scale-\(k\) cell whose index is within \(C_0\) of an occupied index in each coordinate. Choose an endpoint in that occupied cell and apply the closed-cell distance bound.

Choose \(z\in Z\) with \(d_\infty (x,z)\le (C_0+1)2^{k_0}\). The layer bound gives \(C_0 2^k\le d_\infty (y,z)\), while \(2^k\ge 2\cdot 2^{k_0}\). The triangle inequality now yields

If \(k\ne k_0\), then \(k\ge k_0+1\). A shared point has distance zero from itself, contradicting the positive separation.

Euclidean division by \(2^d\) gives a unique integer quotient and a remainder in \(\{ 0,\ldots ,2^d-1\} \) in each coordinate. This proves the membership criterion and the cardinality formula, including negative indices. The identity \(\lfloor t/n\rfloor =\lfloor \lfloor t\rfloor /n\rfloor \) for a positive integer \(n\) gives the point-index identity.

A point’s fine index belongs to \(R_{k-\ell }(I_k)\) if and only if its coarse index belongs to \(I_k\). The cell-membership criterion therefore proves the decomposition of \(D_k\). Multiplying the coarse-cell count by \(4^{k-\ell }\) and applying the endpoint and crossing-edge bounds gives the cardinality estimates.

The inequalities \(\zeta \le 1\) and \(\delta _0\ge 0\) give \(\ell _k\le k\le p_k\), which implies the divisibility relations for the corresponding powers of two. Since each floor exceeds its argument minus one, summing the two floor bounds and substituting \(\zeta =1-\delta _0/2\) yields the exponent bound.

Averaging over coordinate residues mod \(m\) selects residues \((a,b')\) with \(m|B(F;m,a,b')|\le 2|F|\). The fine-cell count gives the first inequality; dividing by \(m=2^{p-\ell }\) and using \(4^{k-\ell }/2^{p-\ell }=r^2/(st)\) gives the second.

The ratio equals \(2^{2k-p_k-\ell _k}\). The exponent bound gives \(2^{2k-p_k-\ell _k}\le 2^{2-\delta _0 k/2}=4\, 2^{-\delta _0 k/2}\).

Evaluating the belt-shift bound at exponent \(\ell =\ell _k\) and pitch \(p=p_k\) and substituting the scale-ratio bound for \(r_k^2/(s_k t_k)\) yields the inequality.

The point \(x\) belongs to a unique layer \(D_k\) with \(k\ge k_0\). Since \(\ell _k\le k\), the decomposition of \(D_k\) into scale-\(\ell _k\) fine cells gives \(z\in F_{k,\ell _k}\) with \(x\in C_{\ell _k,z}\). Conversely, if \(h\ge k_0\), \(w\in F_{h,\ell _h}\), and \(x\in C_{\ell _h,w}\), then \(C_{\ell _h,w}\subseteq D_h\), so \(h=k\), and \(w=c_{\ell _k}(x)=z\).

Every \(x\in \mathbb R^2\) either lies in \(N_{k_0}\) or belongs to the fine cell \(C_{\ell _k,z}\) of its unique pair \((k,z)\) with \(k\ge k_0\) and \(z\in F_{k,\ell _k}\).

The floor description of membership in the real cell at origin zero identifies \(C_{k,z}\) with its integer points. Refining a single index to unit scale gives \(|C_{k,z}|=4^k\). Because integer ancestry agrees with the floor index at origin zero, composing ancestry maps shows that all sites of a fine square share the same coarse index, which gives nesting.

For each \(x\in S\), the unit square \(C_{0,x}=\{ x\} \) is contained in \(S\). With

if \(k{\lt}K\), maximality shows that the parent \(C_{k+1,\lfloor x/2^{k+1}\rfloor }\) is not contained in \(S\), so \((k,\lfloor x/2^k\rfloor )\in \mathcal P_K(S)\). Conversely, every selected square is contained in \(S\). For \((k,u),(l,v)\in \mathcal P_K(S)\) with \(k{\lt}l\) and \(C_{k,u}\cap C_{l,v}\neq \varnothing \), nesting gives

and \(k{\lt}l\le K\), contradicting the selection of \((k,u)\), while at equal scales the common site forces equal indices. Counting the disjoint union gives the sum identity, and restricting its nonnegative summands to scale \(K\) gives the cap bound.

The interval contains \(\lfloor b/u\rfloor -\lfloor a/u\rfloor +1\) integers, and the inequalities \(u\lfloor b/u\rfloor \le b\) and \(a{\lt}u(\lfloor a/u\rfloor +1)\) yield the bound.

Setting \(X=[\lfloor x_0/u\rfloor ,\lfloor x_1/u\rfloor ]\cap \mathbb Z\) and \(Y=[\lfloor y_0/u\rfloor ,\lfloor y_1/u\rfloor ]\cap \mathbb Z\), an inside point places a mixed square’s index in \(X\times Y\), while an outside point in the same square crosses one of the four sides of \(Q\). Monotonicity of integer division then forces the corresponding index coordinate to equal an endpoint of \(X\) or \(Y\). Consequently

and the quotient-interval estimate gives \(u\, \# M_k(Q)\le 2(x_1-x_0)+2(y_1-y_0)+8u\le 4\operatorname {size}(Q)+8u\).

A selected square is nonempty and contained in \(S\), so its parent contains a site of \(S\). For \(k{\lt}K\), the selection condition implies that the parent also contains a site outside \(S\). Every selected index at scale \(k\) therefore belongs to the one-step refinement of \(M_{k+1}(S)\), which has cardinality \(4|M_{k+1}(S)|\).

Because a finite convex hull is compact and convex, its intersection with a horizontal line is a compact interval connecting its attained extrema. Intersecting that interval with \(\mathbb Z\) rounds the lower endpoint upward and the upper endpoint downward, and integer translation commutes with both floor and ceiling, establishing the initial row step in the proof of Lemma 9.4 of [ 286 ] .

Each nonempty sample lies in an integer square of radius \(s_0\) centered at any one of its sites and therefore contains at most \((2s_0+1)^2\) sites, whereas empty samples contribute zero. Summing over the \(N_0\) pieces and using \((2s_0+1)^2\le 9s_0(s_0+1)\) together with \(N_0(s_0+1)\le n\) yields \(|T|\le 9ns_0\).

The coordinate bounds defining \(S_r\) decompose directly into vertical and horizontal intervals to give the row formula. For a finite union \(S=\bigcup _{i\in I}S_i\), any point in \(S_r\setminus S_t\) lies within distance \(r\) of some constituent \(S_i\) while avoiding \((S_i)_t\), which gives the set inclusion and, by union subadditivity, the cardinality bound.

Every supporting slab contains the convex hull of the vertices, and the extrema of each linear form over the finite vertex set are attained. Conversely, for a triangle, dividing the three oriented side functionals by its nonzero signed determinant (of either sign) produces nonnegative barycentric coordinates, while for a rectangle the orthogonal side coordinates in \([0,1]\) produce four nonnegative convex weights; since every allowed normal is a scalar multiple of one of \(x,y,x+y,x-y\), the four supporting strips cut out the polygon.

By Theorem 41.8.1.12, there exist \(l_x,u_x,l_y,u_y\in \mathbb R\) such that \(P\subseteq [l_x,u_x]\times [l_y,u_y]\), which implies

Because each integer interval is finite, their Cartesian product and its subset \(P\cap \mathbb Z^2\) are finite.

Select the \(m\) fan triangles \(P_e\) indexed by \(R\). Because \(T_R\cap \mathbb Z^2\) is nonempty, at least one such triangle contains a lattice point, while Theorem 41.21.4 gives \(1\le m\le 8\). Assigning to each piece \(P_e\) its finite lattice sample \(P_e\cap \mathbb Z^2\) via Theorem 41.8.1.13 (allowing empty individual samples) yields a union equal to \(T_R\cap \mathbb Z^2\) across all shared edges.

By Theorem 41.21.5, every piece lies in the same closed dyadic square of side \(u\), so Theorem 41.5.1 with equal cell indices and radius zero bounds the maximum-norm diameter of each piece and of the total sample by \(u=s_0\). Since \(u\ge 1\) and \(C_B\ge 16\), both \(s_0\) and \(n\) are positive and satisfy

verifying all scale and diameter conditions of a template.

Rounding the real lower strip bounds upward and the upper bounds downward commutes with integer shifts in \(y\), expressing the lower row endpoint as the maximum of three affine functions of slopes \(0,-1,1\) and the upper endpoint as the minimum of three such functions. Pairwise comparisons between these lower and upper affine branches carve out an interval of nonempty rows, and because each affine branch changes by at most one per unit step in \(y\), so do their maximum and minimum.

Intersecting \(S\) with a vertical radius-\(r\) window yields consecutive occupied columns whose horizontal \(r\)-neighborhood is a single interval of width bounded by \(2s_0+2r+1\). Passing from radius \(j-1\) to radius \(j\) shifts any clamped row index by at most one vertical step (moving the horizontal endpoints by at most one) and widens the horizontal radius by one, so each previously occupied row gains at most two sites per end (four in total). Summing at most four new sites across the old occupied rows and adding the two newly occupied extreme rows bounds \(|S_j\setminus S_{j-1}|\) by \(12s_0+12j-2\le 24(s_0+1)\).

Summing the single-piece layer bound across the \(N_0\) pieces (whether overlapping, empty, or disconnected) and applying the template scale bound gives

Every neighbor of a point of \(S\) lies in \(S_1\), so the enclosure loses no crossing edge. Its inclusion into the lattice is injective, as is the induced map on unordered pairs. The endpoint in \(S\) determines the orientation uniquely. The four neighbors change exactly one coordinate by one, proving the radius assertion.

Covering the crossing edges by the four incident edges at each point of \(R\) gives \(|\partial S|\le 4|R|\). The first displayed bound uses the outside endpoints, while for the second, an inside endpoint in \(S_{j-1}\) would put its outside neighbor in \(S_j\), a contradiction. No connectedness or nonemptiness assumption is needed.

An edge leaving \(S\setminus U\) either leaves \(S\) or enters \(U\), and counting the union of these two sets of unordered edges gives the cardinality bound.

For positive \(j\), counting inside endpoints in \(T_j\setminus T_{j-1}\) and applying the depth-layer bound gives \(|\partial T_j|\le 4n\). At \(j=0\), using outside endpoints in \(T_1\setminus T\) gives the same bound because the template assumption \(s_0\ge 1\) permits this layer, so the largest radius \(s_0\) never needs a bound at radius \(s_0+1\). The set-difference estimate then bounds the shell boundary.

Subadditivity gives

Complements are taken in the physical domain. Since \(R\cap B=\varnothing \),

Applying subadditivity to this disjoint union and using purity, \(S_\Omega (X)=S_\Omega (X^c)\), gives

With \(R=A\cap (T_{j-1}\setminus T)\) and \(B=A\cap Y\), these regions are disjoint and \(|B|\le |Y|\le n\). The regional increment bound and \(S_\Omega (B)\le |B|\log q\) (Theorem 42.3.1) give the claim since \(\log q\ge 0\).

Factoring each summand as \((2^k a_k)(2^k)^e\), the cap contributes at most \(A(2^K)^e\). Since \(2^e{\gt}1\), the lower scales contribute at most

For \(x\in Q\subseteq T_j\), choose \(p\in T\) with \(\| p-x\| _\infty \le j\). For every cut endpoint \(z\),

Since \(j\le s_0\le D_0s_0\), this gives \(D_0\operatorname {size}(Q)\le D_0s_0{\lt}\| x-z\| _\infty \). Selected cells are contained in the partitioned set, and their sizes satisfy \(2^k\le 2^K\le s_0\).

The side-length bounds are \(18n\) at scale \(K\) and \(4n\) below it. Applying Theorem 42.21.2 with \(L=s_0\), \(A=18n\), and \(B=4n\), and factoring out \(n\), gives the bound.

Summing the depth-layer estimates gives \(|T_j\setminus T|\le nj\). Disjointness gives \(4^K a_K\le nj\le nL{\lt}2n2^K\), and dividing by \(2^K{\gt}0\) completes the bound.

With \(a_k\) denoting the number of selected squares of side \(2^k\), the mixed-square bound gives \(2^k a_k\le 14n\) for \(k{\lt}K\), and the cap bound gives \(2^K a_K\le 2n\). Applying Theorem 42.21.2 with \(A=2n\), \(B=14n\), and the cap bounds \(2^K\le L{\lt}2^{K+1}\), and factoring out \(n\), gives the bound.

The lattice sup-norm distance, viewed as a real number, is the maximum of the absolute coordinate differences. Increasing \(C\) to \(C_+\) preserves every box bound. Partition the core into maximal contained dyadic squares, capped at the largest power of two not exceeding \(s_0\). For a shell, cap at the largest power of two not exceeding \(L\). Every selected square has side \(u\le s_0\) and lies in \(T_j\) with \(j\le s_0\). Separation gives

Thus the box bound applies at the same real clearance and exponent. Subadditivity over the physical intersections and the weighted core and shell estimates give the first two inequalities. Their factors are nonnegative because \(C_+\ge 0\) and \(2^e-1{\gt}0\). For a prefix, use the shell estimate at depth \(j-1\) and then the partial-row bound \(n\log q\) for the arbitrary subset \(Y\).

Orient a physical crossing edge from \(p\in A\cap U\) to \(q\notin A\cap U\). If \(q\notin A\), then \(p\in Z\), contrary to \(U\cap Z=\varnothing \). Thus \(q\in A\) and \(q\notin U\), and the edge crosses \(U\). Inclusion preserves unordered pairs injectively.

A point \(z\in T_j\cap Z\) would be within distance \(j\le s_0\) of a point of \(T\), contradicting \(4D_0s_0{\lt}\operatorname {dist}_\infty (T,Z)\).

The preceding separation estimate excludes cut endpoints from \(T_j\) and its shell. By Theorem 41.12.1.1 and Lemma 41.8.2.5,

The core is the case \(j=0\). The manuscript fixes \(D_0{\gt}2R+10\), which implies \(D_0\ge 1\) for \(R\ge 0\).

Choose \(q\in T\) with \(\| p-q\| _\infty \le j\). The triangle inequality gives \(\| p-z\| _\infty \ge \| q-z\| _\infty -j{\gt}4D_0s_0-j\). Since \(s_0{\gt}0\), \(D_0\ge 1\), and \(j\le s_0\), we have \(4D_0s_0-j{\gt}D_0s_0\ge D_0u\). Both endpoints of every crossing edge belong to \(Z\). The integer interval description follows directly from the half-open dyadic square inequalities.

Let \(x\) be joined to \(y\in A\cap T_L\) by a path of length at most \(R\). Then \(T\) is nonempty. The depth \(d(v)=\min _{t\in T}\| v-t\| _\infty \) satisfies \(d(y)\le L\) and changes by at most one along each graph edge. Every endpoint of a prefix of the path therefore has depth at most \(L+R\). If the path leaves \(A\), its first crossing gives a physical cut endpoint of depth at most \(L+R\), contrary to the hypothesis. Thus \(x\in A\); the depth bound at \(x\) gives \(x\in T_{L+R}\).

By Theorem 41.12.1.5, every \(x\in N_R^\Lambda (S)\) belongs to \(A\) and to \(T+[-(L+R),L+R]^2_{\mathbb Z}\). Thus it lies outside \(\Lambda \setminus A\). The dilation gives a point \(t\in T\) with \(\| t-x\| _\infty \le L+R\), so the strict clearance from \(J\) implies \(x\notin J\). Both parts of the union are therefore excluded.

A site of \(C_{k,z}\) inside a union belongs to some \(S_a\), whereas a site outside the union lies outside every \(S_a\), so \(C_{k,z}\) is mixed for \(S_a\). For \(S\setminus U\), a site inside \(S\setminus U\) lies in \(S\) and outside \(U\), while a site outside \(S\setminus U\) either lies outside \(S\) or belongs to \(U\); hence \(C_{k,z}\) is mixed for either \(S\) or \(U\).

The four pairs of integer supporting inequalities describe the rows of \(S_a\). Since their slopes lie in \(\{ -1,0,1\} \), clamping \(x\) into a nonempty row \(z\) shifts the horizontal coordinate by at most \(d\). For the dilated piece \((S_a)_j\), first clamp the source row of \(S_a\) into the window of radius \(j\) around \(z\); because the nonempty rows of \(S_a\) form a consecutive interval, this row is nonempty. Applying the undilated estimate and clamping the horizontal coordinate within radius \(j\) yields \((w,z)\).

In an interior block of \(u\) rows, every row of \((S_a)_j\) is nonempty. Moving an inside site and the two endpoints of a reference row by at most \(u\) shows that any mixed square has column index within \(2\) of an endpoint’s column index, leaving at most \(10\) columns in each interior row block. In the first and last occupied row blocks, every mixed square meets the bounding box of \((S_a)_j\). If \(N_x\) and \(N_y\) denote the numbers of column and row blocks meeting this bounding box, then

which gives the stated bound (and when \(S_a\) is empty, \(M_k((S_a)_j)\) is empty).

Integer dilation commutes with the finite union of sampled pieces. Summing the single-piece mixed-square bounds and using \(24N_0(s_0+1)\le n\) gives the bounds for \(T\) and \(T_j\); the bound for \(T_j\setminus T\) follows by subadditivity.

Each selected square at level \(k{\lt}K\) has a mixed parent at level \(k+1\), and each parent has four children, so \(uN_k\le 2(2u)|M_{k+1}(T_j\setminus T)|\). The shell mixed-square bound and \(24N_0u\le n\) give \(uN_k\le 2(3n+96N_0u)\le 14n\).

The selected squares at the cap \(K\) are pairwise disjoint inside \(T\), so \(4^K N_K\le |T|\le 9ns_0\le 18n2^K\). For \(k{\lt}K\), every selected square has a mixed parent with four children, and \(2^{k+1}\le 2^K\le s_0\), so

using \(24N_0s_0\le n\).

The threshold gives \(d\le k\) and \(\zeta k=k-10^{-7}k\le k-d\). Taking the floor proves the first inequality. Likewise \((1+\delta _0)k\ge k+2d\ge k+d\), so its floor is at least the integer \(k+d\).

Applying the increasing function \(n\mapsto 2^n\) to the two index inequalities of the preceding theorem and using \(2^{a+b}=2^a2^b\) yields both bounds.

By the unboundedness of powers of two, there is a nonnegative integer \(d\) with \(M{\lt}2^d\); for \(K=10^7d\) and every \(k\ge K\), the preceding theorem gives \(2^dt_k\le r_k\) and \(2^dr_k\le s_k\). Since the cell sides are positive, replacing \(2^d\) by \(M\) proves both inequalities.

Set \(a=\delta _0\log 2/4{\gt}0\). Since \((k+1)^p\exp (-ak)\to 0\) as \(k\to \infty \), there exists \(K\ge 0\) such that \((k+1)^p2^{-\delta _0 k/4}\le 1\) for all \(k\ge K\). Multiplying by \(2^{-\delta _0 k/4}\) gives the inequality.

Set \(q=2^{-\delta _0/4}\in (0,1)\). By the preceding theorem, \(w_p(k)\le q^k\) for all sufficiently large \(k\), so convergence follows by comparison with the geometric series \(\sum _{k\ge 0}q^k\).

Let \(S\ge 0\) be the sum of the series \(\sum _{k=0}^\infty w_p(k)\) and set \(B=S+1{\gt}0\). Since \(w_p(k)\ge 0\), every finite partial sum is at most \(S{\lt}B\).

The exact cell union gives \(D_k=\bigcup _{z\in I_k}C_{k,z}\). Intersect this finite union with \(U_j\) and commute closure with the finite union. Empty intersections have empty closures, so retaining precisely the indices in \(J_j\) leaves the union unchanged.

A point of the nonempty intersection lies below both upper endpoints in each coordinate. It lies at or above the cell’s lower endpoint and strictly above the pitch interior’s lower endpoint. Hence the maximum lower endpoint is strictly below the minimum upper endpoint. The coordinate intersection contains the open interval between these endpoints and is contained in their closed interval. Taking closures therefore gives that closed interval. Closure commutes with products, proving the rectangle formula.

Containment in the closed cell follows from monotonicity of closure. Apply the closed-cell distance bound with identical cell indices and index radius zero. This gives the pointwise distance bound, and hence the diameter bound.

Monotonicity of closure gives \(R_j\subseteq \overline{U_j}\). This closure is contained in the product of the closed intervals \([v_{j,q}+t,v_{j,q}+s]\), for \(q=1,2\). Two points in this product have coordinate differences at most \(s\), proving the distance and diameter bounds.

Distinct integer indices differ in at least one coordinate. Suppose \(i_q{\lt}j_q\). The upper endpoint for index \(i_q\) is at most \(o_q+t(a,b)_q+sj_q\), while the lower endpoint for index \(j_q\) is \(o_q+t(a,b)_q+sj_q+t\). Thus the two coordinate intervals are separated by at least \(t\). Taking the maximum coordinate distance proves the separation claim; the other ordering is symmetric.

If \(k=h\), then \(i\ne j\) and the shifts agree, so Theorem 41.15.4 gives \(\| x-y\| _\infty \ge t_k\).

If \(k{\lt}h\), equality of parity gives \(k+2\le h\). The containments \(R_{k,i}\subseteq \overline{D_k}\) and \(R_{h,j}\subseteq \overline{D_h}\) and Theorem 41.5.3 give \(\| x-y\| _\infty \ge (C_0-1)r_h/2\ge r_k/2\). If \(h{\lt}k\), apply the same theorem with the layers and points exchanged to obtain \(\| x-y\| _\infty \ge (C_0-1)r_k/2\ge r_k/2\). Each case gives the stated minimum bound.

Put \(N=2^{p-k}\), so \(s=Nr\), and let \(q_i=\lfloor (v_{j,i}-o_i)/r\rfloor \). If a cell indexed by \(z\) meets \(U_j\), a point in that intersection lies above \(v_{j,i}\) and below \(v_{j,i}+s\). The half-open cell inequalities and the defining floor inequalities consequently give, for each coordinate \(i\in \{ 1,2\} \),

Thus \(J_j\) lies in an integer rectangle with \(N+1\) indices in each coordinate. Its cardinality is at most \((N+1)^2\), which is at most \((N+2)^2\).

Since \(0\le \zeta \le 1\), multiplication by \(\zeta \) and taking floors preserve the order of the layer indices. Also \(\zeta (k+1)\le \zeta k+1\), and adding one commutes with taking the floor. Therefore \(\ell _k\le \ell _{k+1}\le \ell _k+1\). Exponentiating the two possible integer values gives the side-length assertion.

The endpoints of each nonempty fragment have the form \(o_i+m\) with integers \(m\), and the lower endpoint is strictly below the upper one. Their difference is therefore at least one, so each piece contains a lattice point and the template is nonempty. Since \(R_j\) is the union of its fragments \(F_{j,z}\), the lattice points of the pieces are exactly those of \(R_j\), and the piece and template diameters follow from the diameter bounds for \(F_{j,z}\) and \(R_j\).

Put \(m=p_k-k\). Since \(p_k\le (1+\delta _0)k\), we have \(2^m\le r^{\delta _0}\). As \(2^m\ge 1\),

If \(C_{\rm tpl}\le 0\), the first bound is trivial. Otherwise, since \(r\ge 1\),

Also \(s_k=2^{p_k}\le r^{1+\delta _0}\le r^{1+2\delta _0}\le n_k\) because \(C_P\ge 1\).

Every point of \(T\) lies in \(R_j\subseteq \overline{D_k}\). The layer distance estimate gives endpoint distance at least \(C_0r{\gt}4D_0r=4D_0s_0\).

Put \(e=1+2\delta _0\) and \(C=\max \{ C_P,0\} +1\), so \(n_k\le Cr^e\). Whenever \(a{\lt}b\), the ratio \(Cr^a/r^b=Cr^{-(b-a)}\) tends to \(0\) as \(k\to \infty \). Because the exponent gaps give \(e(1-\ell ){\lt}1\) and \(e\beta {\lt}\zeta \), and the fine side satisfies \(r^\zeta /2\le t_k\le r\), this decay yields the three upper bounds on \(\lfloor n_k^{1-\ell }\rfloor \) and \(n_k^\beta \). When \(C_P{\gt}0\), the lower bound \(n_k\ge C_P\, r\) tends to infinity with \(k\).

Only the reverse implication needs proof. A point \(x\in D_k\cap U_j\) belongs to a cell \(C_{k,z}\) with \(z\in I_k\). Since \(L_{z,i}\le x_i\le H_{z,i}\), monotonicity of the floor gives \(q_{z,i}^-\le \lfloor (x_i-o'_i)/s\rfloor \le q_{z,i}^+\). From \(x\in U_j\) we have \(j_i{\lt}(x_i-o'_i)/s{\lt}j_i+1\), so \(\lfloor (x_i-o'_i)/s\rfloor =j_i\) and \(j\in B_z\).

Since \(k\le p\), we have \(r\le s\). In each coordinate, \(H_{z,i}=L_{z,i}+r\le L_{z,i}+s\), so

Hence \(|B_z|\le 4\) for every \(z\in I_k\), and summing over \(z\in I_k\) gives \(|\mathcal P_k|\le 4|I_k|\).

Combine \(|\mathcal P_k|\le 4|I_k|\) with \(|I_k|\le 8(2C_0+1)^2|\partial _\Lambda A|\).

The scale order gives \(k\le p_k\), so the primary count is at most \(32(2C_0+1)^2b\), where \(b=|\partial _\Lambda A|\). Since \(2^k\ge 1\) and \(1+2\delta _0\ge 1\), the ceiling satisfies \(n_k\ge C_P(2^k)^{1+2\delta _0}\ge C_P2^k{\gt}0\). The inequality \(100\ge \delta _0/2\) and \(k\ge 0\) give

Apply the uniform finite-sum estimate at exponent zero, obtaining \(B_0{\gt}0\) before \(F\). Multiplication by the nonnegative count bound and summation give the conclusion with \(M=32\bigl(C_P^{100}\bigr)^{-1}B_0{\gt}0\).

Each coordinate of \(e/2\) lies in \([0,1]\), so both coordinates of each mark lie in the corresponding closed cell intervals.

Since \(2^\ell {\gt}0\), distinct elements of \(\{ 0,1,2\} ^2\) yield distinct points, and there are nine such elements.

The cardinality of a finite union is at most the sum of the cardinalities of its members, each of which has nine points.

For the sparse-belt pair of residues \((a,b)\), multiplying the belt-cell count by \(9\) gives the coefficient \(9\cdot 64=576\).

The scale-ratio estimate with exponent gap five gives \(32t_k\le 2^k\). The nonadjacent-layer bound gives \(\| x-y\| _\infty \ge (C_0-1)2^{\max (k,h)}/2\ge 2^k/2\ge 16t_k\).

A difference of at least two would give distance at least \(16t_k\), contradicting the strict upper bound since \(t_k{\gt}0\).

A mark of a cell of side \(2^j\) is \(o+2^j(z+e/2)\), where \(e\in \{ 0,1,2\} ^2\). Since \(\ell \le j+1\), the vector \(2^{j+1-\ell }(2z+e)\) is integral, and the mark equals \(o+(2^\ell /4)2^{j+1-\ell }(2z+e)\).

At least one coordinate of the integer vectors indexing \(x\) and \(y\) differs. Its difference has absolute value at least one, so the corresponding coordinate difference of \(x\) and \(y\) has absolute value at least \(q\).

If \(u=v\), use the point-separation bound. Otherwise, the supporting line has a constant coordinate, coordinate sum or coordinate difference. Its value at a missing mesh point differs from the line’s value by a nonzero integer multiple of \(q\). A coordinate difference is bounded by the sup distance; a difference of sums or differences is bounded by twice that distance. The result follows.

If \(a=b\), then \(x=a\ne p\), so mesh-point separation gives the stronger bound \(q\). Otherwise let \(L\) be the supporting line of \([a,b]\). If \(p\notin L\), apply the line-clearance estimate. If \(p\in L\setminus [a,b]\), one endpoint \(e\in \{ a,b\} \) lies between \(p\) and \(x\). Since \(p\ne e\), mesh-point separation and distance additivity give

In both cases the asserted half-spacing bound follows.

Write a point of \([a,b]\) as \((1-t)a+tb\), where \(0\le t\le 1\). Its distance from \(a\) is \(t\| b-a\| =t\). It therefore belongs to the closed ball precisely when \(0\le t\le \eta \). These points form the segment on the right-hand side.

Under a sparse pair of residues at each scale, the integer counts \(|F_k|\) are dominated by a fixed multiple of a summable geometric sequence. Their real-valued series is therefore summable, so its terms tend to zero and \(|F_k|{\lt}1\) eventually, forcing \(F_k\) to be empty outside finitely many indices.

Let \(B_0{\gt}0\) be the uniform finite-sum constant for the zero polynomial exponent, and set \(B=576B_0\). The union of the marks over the finite support restricted to \(k\ge k_0\) has the stated membership condition. Since a finite union has at most the sum of the individual cardinalities and each cell contributes at most nine marks, its count is at most

where \(H\) is the finite retained support.

Suppose that the distance is less than \(t_k/4\). Each mark is in the closure of its layer. Layer locality forces \(k\le h+1\). Monotonicity and the adjacent-scale estimate give \(\ell _k\le \ell _h+1\), so both marks lie on the translated mesh of spacing \(t_k/4\). Distinct mesh points cannot be closer than this spacing. Reversing \(k\) and \(h\) proves both lower bounds and hence their maximum.

For each \(v\in M\), the least layer index \(k(v)\ge k_0\) with an incident cell defines \(s(v)=2^{\ell _{k(v)}}{\gt}0\). Because the exponent \(\ell _k\) is nondecreasing in \(k\), \(s(v)\) is a smallest incident side realized at layer \(k(v)\).

For the counted finite union and residues from the uniform initial-mark bound, taking the least layer index admitting an incident selected cell at each point of \(M\) gives a positive smallest incident side because the fine-cell exponent is nondecreasing. Applying fine-layer mark separation to the two cells realizing \(s(v)\) and \(s(w)\) then gives the pairwise distance bound (which is vacuous when \(M\) is empty).

The coordinate description of \(\overline Q\) gives \(x\in \overline Q\) if and only if \(|x_j-c_j|\le r\) for \(j=1,2\). These inequalities are equivalent to \(\| x-c\| _\infty \le r\).

The center has relative coordinates \((1/2,1/2)\). Every segment endpoint is a corner or side midpoint, so both relative coordinates belong to \(\{ 0,1/2,1\} \).

Each of the four sides contributes either one or two elementary segments.

Every point of \(Q\) lies on the segment from \(c\) to some point of the perimeter. Every perimeter point belongs to an elementary segment, so it lies in the corresponding fan triangle. Conversely, every vertex lies in \(Q\), and convexity keeps each triangle in \(Q\).

A point different from \(c\) determines a unique perimeter point on the ray from \(c\). It belongs to both triangles if and only if that perimeter point lies in \(e\cap e'\). The center \(c\) belongs to every triangle.

Since neither residue is selected, each shifted coordinate remainder lies between \(1\) and \(m-1\). The open fine-cell interior therefore lies inside \(I_{a,b}(j(z))\) and belongs to \(D_k\). Its closure is \(\overline{Q_\ell (z)}\), so taking closures gives the inclusion even when a side of the fine cell meets the boundary of \(I_{a,b}(j(z))\).

The open fine square is nonempty and lies in \(D_k\cap I_{a,b}(j(z))\), so the pitch index \(j(z)\) is retained. If two distinct primary birth regions contained \(\overline{Q_\ell (z)}\), an interior point would belong to both, contradicting their positive separation within the layer.

In the affine parametrization of a side, one relative coordinate is \(\pm 2^\ell /2\) and the other is \((2^\ell /2)u\) with \(|u|\le 1\). The whole side and either midpoint half satisfy this bound, so the maximum of the two absolute coordinates is \(2^\ell /2\).

The defining determinant \(\det (a_e-c,b_e-c)\) is nonzero. Thus the two edge vectors are linearly independent and span the plane, and the three vertices affinely span \(\mathbb R^2\). Their convex hull consequently has nonempty interior.

The convex hull of these finitely many vertices is closed. A convex set with nonempty interior has the same closure as its interior, so \(\overline{\operatorname {int}(P_e)}=\overline{P_e}=P_e\).

Let \(\phi \in \Phi \). From the whole-side endpoint and midpoint-subdivision formulas, the two perimeter vertices \(a_e,b_e\) of \(P_e\) lie in a single closed half-plane through \(c\): either \(\phi (a_e),\phi (b_e)\ge \phi (c)\) or \(\phi (a_e),\phi (b_e)\le \phi (c)\).

In the first case, convexity places \(P_e\) in \(\phi ^{-1}([\phi (c),\infty ))\). Because \(\phi \) is a surjective continuous linear functional, it is an open map, so the interior of this half-plane is \(\phi ^{-1}((\phi (c),\infty ))\). Hence \(\phi (x){\gt}\phi (c)\) for every \(x\in \operatorname {int}(P_e)\). Replacing \(\phi \) by \(-\phi \) handles the second case.

The homothety \(H(y)=c+(y-c)/2\) fixes \(c\) and maps the two perimeter vertices of \(P_e^{\rm L}\) to those of \(P_e^{\rm S}\), so \(H(P_e^{\rm L})=P_e^{\rm S}\).

Any \(x\in P_e^{\rm L}\) has the form \(x=c+\lambda (y-c)\) with \(0\le \lambda \le 1\) and \(y\) on the base of \(P_e^{\rm L}\). Since \(\| y-c\| _\infty =2r\), we have \(\| x-c\| _\infty =2r\lambda \). Thus \(x\in \overline B_\infty (c,r)\) if and only if \(\lambda \le 1/2\), which is equivalent to \(x=c+2\lambda (H(y)-c)\in P_e^{\rm S}\).

The closure of \(Q\) is the product of the closed coordinate intervals with lower endpoints \(c_1-\rho \) and \(c_2-\rho \) and length \(2^m=2\rho \). Their upper endpoints are \(c_1+\rho \) and \(c_2+\rho \), so their product is \(\overline B_\infty (c,\rho )\).

Since \(k\ge 50{,}000{,}000\), we have \(\ell _k\ge 5\) and \(2^{\ell _k}=32\cdot 2^{\ell _k-5}\). Dividing by \(128\) proves (205).

Since \(v\) belongs to the closed fine cell, it belongs to the closed layer \(\overline{D_k}\). The distance condition defining \(D_k\) shows that \(Z\) is nonempty, so the closed initial regions \(X_i^0\) cover \(\mathbb R^2\). From \(k\ge k_0\) we obtain \(\ell _k\ge 5\) and \(2r=t_k/32\).

Set \(S_s=\operatorname {int}(P_s^{\rm L})\) and \(W=B_\infty (v,2r)\). Because \(\bigcup _sP_s^{\rm L}=\overline B_\infty (v,2r)\), taking interiors gives \(S_s\subseteq W\). Each \(S_s\) is nonempty and connected.

No \(S_s\) meets the boundary \(\partial X_i^0\) of any initial region: a point \(x\in S_s\cap \partial X_i^0\) would satisfy \(\| x-v\| _\infty {\lt}t_k/32\), forcing \(x-v\) to lie along one of the four allowed directions through \(v\), whereas the open triangle \(S_s\) is disjoint from those four lines. Since the sets \(X_i^0=\overline{U_i}\) cover \(S_s\) and \(\partial X_i^0\cap S_s=\varnothing \), connectedness of \(S_s\) and pairwise disjointness of the open sets \(U_i\) imply that \(S_s\subseteq U_{\sigma (s)}\) for a unique \(\sigma (s)\in \mathcal I\).

Put \(D=\bigcup _sS_s\), so \(\overline D=\bigcup _sP_s^{\rm L}=\overline B_\infty (v,2r)\). For \(i\in \mathcal I\), the finite union \(E_i=\bigcup _{\sigma (s)=i}P_s^{\rm L}\) is closed and satisfies \(U_i\cap D\subseteq E_i\). Since \(U_i\) and \(W\) are open and \(W\subseteq \overline D\),

Conversely, taking closures of \(S_s\subseteq U_i\) gives \(E_i\subseteq X_i^0\). Since \(\overline B_\infty (v,r)\subseteq W\), intersecting with \(\overline B_\infty (v,r)\) and applying \(P_s^{\rm L}\cap \overline B_\infty (v,r)=P_s^{\rm S}\) yields the stated decomposition.

The closed restriction of the assignment gives \(P_s^{\rm S}\subseteq X_{\sigma (s)}^0\) for each \(s\): the triangle is one of the terms in the union describing \(X_{\sigma (s)}^0\cap \overline B_\infty (v,r)\).

Suppose first that \(b_s^+=b_t^-\), and put \(e=b_s^+\). The base-radius identity gives \(\| e-v\| _\infty =r{\gt}0\), so \(e\ne v\). Each triangle is the convex hull of its center and two base endpoints. Consequently,

When \(b_t^+=b_s^-\), interchange \(s\) and \(t\) to obtain the same nondegenerate shared radial segment. If \(\sigma (s)\ne \sigma (t)\), the theorem on shared boundary segments of initial regions gives \(\chi (\sigma (s))\ne \chi (\sigma (t))\). Conversely, equality of the identifiers gives equality of their colors.

Each edge of \(G\) joins adjacent sectors of the same color. Because adjacent sectors with distinct identifiers have opposite colors, their assigned identifiers agree. Consequently \(\sigma \) is constant on each connected component of \(G\) and descends to a unique map \(\lambda :\mathcal R\to \mathcal I\) with \(\lambda ([s])=\sigma (s)\).

By definition of \(\sigma \), \(X_i^0\cap \overline B_\infty (v,r)=\bigcup _{\sigma (s)=i}P_s^{\rm S}\). Grouping the sectors \(s\) with \(\sigma (s)=i\) by their connected components \(R\in \mathcal R\) yields the decomposition into the run regions \(Y_R\).

Since adjacent bases have equal identifiers and therefore equal colors, the cyclic adjacency graph on \(\mathcal J\) is a connected subgraph of \(G\). Hence \(G\) has a single connected component, and \(\sigma \) is constant with some value \(i_0\in \mathcal I\).

For each triangle of the larger fan, \(\operatorname {int}(P_s^{\rm L})\subseteq U_{i_0}\). Taking closures and using the regularity of the fan triangles and birth regions gives \(P_s^{\rm L}\subseteq X_{i_0}^0\). The fan cover and centered-cell identities then yield

Taking interiors gives \(B_\infty (v,2r)\subseteq U_{i_0}\). Since \(r{\gt}0\), we have \(\overline B_\infty (v,r)\subseteq B_\infty (v,2r)\subseteq U_{i_0}\). Because \(v\in \overline B_\infty (v,r)\) and the open regions \(U_i\) are pairwise disjoint, \(i_0\) is unique.

With \(K=\sigma (\mathcal J)\) and \(E_i=\bigcup _{\sigma (s)=i}P_s\) for each \(i\in K\), the sets \(E_i\) form a finite closed family covering \(\overline B_\infty (v,r)\). By (217), \(X_i^0\) and \(E_i\) agree on a neighborhood of every point of \(B_\infty (v,r)\), so their interior membership agrees there, while an index outside \(K\) has no birth-region point in this neighborhood.

Suppose that \(x\in \partial X_i^0\) and \(x\ne v\). The finite-cover frontier bound gives a distinct index \(j\in K\) with \(x\in E_i\cap E_j\), since its outer-boundary alternative is excluded by \(x\in B_\infty (v,r)\). Hence there are \(s,t\in \mathcal J\) with \(\sigma (s)=i\), \(\sigma (t)=j\) and \(x\in P_s\cap P_t\). Both triangles also contain \(v\), so their intersection is nontrivial, and the fan-triangle contact classification gives, after interchanging \(s\) and \(t\) if necessary, \(b_s^+=b_t^-\) and \(P_s\cap P_t=[v,b_s^+]\). Since \(i\ne j\), this pair is active.

If \(x=v\) and no pair is active, every adjacent pair has the same assigned index, which places the smaller closed square in a single open region \(U_j\). A point of \(U_j\) lies on no birth-region boundary: it is interior to \(X_j^0\), and disjointness of the open regions, together with \(X_i^0=\overline{U_i}\), excludes membership in \(X_i^0\) for \(i\ne j\). Thus a boundary point at \(v\) forces an active pair, whose radial segment contains \(v\).

Conversely, let \((s,t)\in \mathcal A\) and \(x\in [v,b_s^+]\). The exact fan-intersection formula includes this segment in \(P_s\cap P_t\): the common base endpoint belongs to both bases, and its radial join with \(v\) belongs to both triangles. By (217), \(x\in X_{\sigma (s)}^0\cap X_{\sigma (t)}^0\). Since the two indices are distinct, \(U_{\sigma (s)}\) is disjoint from \(X_{\sigma (t)}^0=\overline{U_{\sigma (t)}}\). Hence \(x\notin U_{\sigma (s)}\) and \(x\in \partial X_{\sigma (s)}^0\), as required.

The fan radius is positive. Consequently, \(\overline B_\infty (v,r/2)\subseteq B_\infty (v,r)\), and the open-square equivalence applies to every point of this closed square.

Endpoint adjacency is exactly the successor relation, so the active pairs are \((s,\tau (s))\) with \(s\in \mathcal A_*\). The active radial description on the smaller closed square therefore identifies the boundary points with the segments \([v,b_s^+]\) at these changes. Since \(\overline B_\infty (v,r/2)\subseteq \overline B_\infty (v,r)\), restricting each radial segment to the square replaces \([v,b_s^+]\) by \(R_s\) throughout the smaller closed square. This includes the center, and proves 221.

Because \(x\) belongs to both closed layers, \(|h-k|\le 1\), and thus the fine exponents satisfy \(\ell _k\le \ell _h+1\). Put \(t=2^{\ell _k}\). The corner \(x\) lies in \(o+(t/2)\mathbb Z^2\), so its coordinate along \([a,b]\), measured from \(a\) in units of \(t/2\), is an integer in \(\{ 0,1,2\} \), giving \(a\), \((a+b)/2\), or \(b\).

Substituting the four side indices into the affine parametrization of the fan boundary produces the displayed coordinate pairs, with the corner pairs \((\varepsilon _s,\eta _s)\) given in the same order by \(((1,0),(1,1))\), \(((1,1),(0,1))\), \(((0,1),(0,0))\) and \(((0,0),(1,0))\).

Parametrize side \(s\) by a signed coordinate \(u\in [-1,1]\), with affine parameter \((u+1)/2\in [0,1]\). An undivided side has initial and final signed coordinates \(-1\) and \(1\), giving affine parameters \(0\) and \(1\). Half \(h\in \{ 0,1\} \) of a subdivided side has signed coordinates \(h-1\) and \(h\), giving affine parameters \(h/2\) and \((h+1)/2\).

In the affine parametrization of \([a,b]\) by \([0,1]\), the endpoints \((u,v)\) have parameters \((0,1)\) for an undivided side, \((0,1/2)\) for the first half, and \((1/2,1)\) for the second half. Each interval is contained in \([0,1]\).

This is the defining condition for \(\varepsilon _s=1\).

Every elementary segment lies on its full side \([a_s,b_s]\), so any corner of cell \(w\) on \([a_s,b_s]\) is \(a_s\), \((a_s+b_s)/2\), or \(b_s\). If side \(s\) is undivided, the midpoint \((a_s+b_s)/2\) cannot be a corner of cell \(w\) by definition of the subdivision rule. If side \(s\) is subdivided, each half-side excludes the opposite endpoint of \([a_s,b_s]\) and has the remaining two points as its endpoints.