The halving-line problem and earlier bounds

A \(k\)-set of a planar point configuration is a \(k\)-point subset strictly separable from the remaining points by a line. The \(k\)-set problem asks for the largest possible number of these subsets at a specified size and rank. Halving pairs concern its middle rank and measure the complexity of balanced line separations.

The early work of Lovász and of Erdős, Lovász, Simmons and Straus established the \(O(n^{3/2})\) scale for halving lines and developed the rotating-line and dissection-graph viewpoint (Lovász 1971; Erdős et al. 1973). Pach, Steiger and Szemerédi improved the upper bound by an iterated-logarithm factor (Pach et al. 1992). Dey then proved the bound \(O(n(k+1)^{1/3})\) for \(k\)-sets with \(1\le k\le n/2\), giving \(O(n^{4/3})\) for halving lines (Dey 1998). His use of convex chains and graph crossings provides the finite starting point of the present argument.

The lower bounds developed on a different scale. Erdős, Lovász, Simmons and Straus constructed configurations with \(\Omega(n\log n)\) halving lines (Erdős et al. 1973). Tóth obtained \(n\exp(\Omega(\sqrt{\log n}))\) halving pairs, and Nivasch subsequently simplified the construction and improved its exponential constant (Tóth 2001; Nivasch 2008). These bounds remain far below a fixed power \(n^{1+\delta}\). More recently, Alonso, López and Rodrigo improved a lower-order term in the upper bound while retaining the exponent \(4/3\) (Alonso et al. 2024).

A related route through measures was developed by Pinchasi (Pinchasi 2009). A line avoiding the point set and leaving half its points on each side gives a balanced cut. Pinchasi studied the changes between such cuts ordered by slope and related endpoint-change bounds to planar measure concentration. Our activity parameter also counts points that change status during an interval and later return; Section 2 supplies the reduction from that parameter to endpoint changes, uniformly over all ranks.

Rank sweeps and the stronger conclusion

For the sweep arguments, call a configuration generic if no three points are collinear, its first coordinates are distinct, its determined slopes are distinct, and no proper intersection of two determined segments lies on a third determined segment. Section 2 justifies reducing the halving-pair theorem to this case.

Fix a generic configuration and an integer rank \(0\le k\le n\). For a slope \(s\) distinct from the determined slopes, mark the \(k\) points with smallest values of \(y-sx\). As \(s\) increases, the marked set changes by exchanging one point for another. We call such a change a switch. For an interval of this sweep, its activity is the number of distinct points whose membership changes. At the middle rank, halving pairs are exactly the switches. Write \(S_k(P)\) for the total number of switches as the slope ranges from \(-\infty\) to \(+\infty\).

The uniformity in \(k\) is needed even for the middle-rank conclusion: restricting a block of switches to its participating points changes the rank. At ranks \(0\) and \(N\) the marked set is constant and \(S_k(P)=0\).

The same uniformity gives a bound throughout the planar \(k\)-set range. For an arrangement \(\mathcal L\) of nonvertical straight lines, let \(\Lambda_k(\mathcal L)\) be the closure of the points on its lines with exactly \(k\) lines strictly below them. Write \(\operatorname{comp}(\Lambda_k(\mathcal L))\) for the total number of vertices and edge pieces of this polygonal chain.

The all-ranks theorem first bounds each level in an arrangement of a given size. A shallow cutting covers a low level by \(O(n/(k+1))\) cells, each crossed by only \(O(k+1)\) lines; within each cell, the level has a fixed local rank. Applying the uniform bound in every cell gives the dependence on \(k\) above. The full argument, including the passage from levels to \(k\)-sets, appears in Section 8.1 after the main theorem is proved.

This corollary concerns planar point sets and complete straight lines only; it asserts no corresponding saving for pseudolines or line segments.

Proof strategy

The central estimate concerns disjoint intervals of sweep steps with activity at least \(b\). The usual crossing argument bounds their number by \(O((n/b)^{4/3})\). We prove a uniform little-\(o\) improvement of this packing bound as \(n/b\) tends to infinity. Choosing one sufficiently large fixed scale then gives a contracting recurrence and the power saving in Theorem 1.

Here is the geometric mechanism behind the packing improvement. For an interval whose endpoint marked sets differ, let \(L\) be the points marked only at its start and \(G\) those marked only at its end. If \(|L|=|G|=a\), joining every point of \(L\) to every point of \(G\) gives a complete bipartite exchange graph with \(a^2\) edges. Convex and concave chain partitions control its crossings. If the packing bound were attained to within a constant factor, we could pass to limiting measures of vertices, edges, and crossings after assigning points compact rank coordinates. Each such coordinate is a smoothed fraction of a family of convex chain graphs lying below the point. Two separated time windows provide a pair of rank coordinates that parametrizes the plane. The crossing counts imply that a positive portion of edge activity has an absolutely continuous projection in such a coordinate pair.

Compact rank coordinates alone do not control physical distances: a small region in the rank square could represent a highly distorted part of the original plane. We use the order of the sweep directions to recover Euclidean control on a positive part of the limiting measure. The coordinates belonging to other time windows become coordinatewise monotone functions. Their almost-everywhere derivatives force three transverse families of sweep lines to have three transverse limiting directions. A local rigidity lemma for these three families prevents collapse after a suitable linear normalization. Crucially, its limits are taken first at a fixed small rank scale and then far enough along the sequence of configurations. We preserve that order when passing to a Hausdorff limit of coordinate graphs.

The crossing bound also makes edge endpoint mass absolutely continuous with respect to vertex mass. Together with the absolutely continuous edge projection in the rank square, this lets us select a portion with positive original edge activity whose vertex projection has bounded density there. The geometric control transfers this vertex measure to the normalized Euclidean plane, where a disk of radius \(r\) has mass \(O(r^{32/17})\), and hence a thin strip of width \(r\) has mass \(O(r^{15/17})\). In a fixed bounded region, the active vertices of a narrow angular window lie either in three such strips or among vertices accounted for by marked tokens crossing the boundary. A token follows a marked point through the successive exchanges. Each token crosses that boundary only a bounded number of times. Summing these activity bounds contradicts the positive limiting edge mass. The exponents \(32/17\) and \(15/17\) are auxiliary spatial exponents; the final saving \(\varepsilon\) comes from the separate fixed-scale recurrence.

Section 2 proves the finite reductions and states the uniform packing estimate. Section 3 constructs the rank coordinates and limiting measures. Sections 4 and 5 establish the directional and metric control, and Section 6 constructs the spatial measure. Section 7 proves the boundary estimate and packing contradiction. Section 8 completes the finite induction and derives the \(k\)-set and level bounds.

A pair of rank coordinates parametrizes the plane

For a nonempty window \(J\), extend every chain in its convex partition to a full convex piecewise linear graph. On the left choose a ray slope between the left endpoint of the window span and the first edge slope; on the right choose one between the last edge slope and the right endpoint of that span. Add affine graphs until there are exactly \(M\) graphs, denoted \(g_{J,1},\ldots,g_{J,M}\). All their slopes lie in a closed interval \([\ell_J,u_J]\) strictly inside the window span. The finitely many choices of ray slopes and affine translates can avoid all proper crossings between an edge in \(J\) and an edge outside \(J\). At each such crossing exactly one of these \(M\) graphs passes through the crossing point: its actual edge graph. This uses the genericity assumption excluding a third determined segment through a proper crossing. For an empty window use arbitrary affine graphs; assertions about any fixed finite collection of windows are made after those windows have become nonempty.

Choose a continuous strictly positive probability density on \(\mathbb R\) with distribution function \(\Phi\). For a sufficiently small \(\varepsilon_J>0\) put \[r_J(x,y)=\frac1M\sum_{i=1}^M \Phi\!\left(\frac{y-g_{J,i}(x)}{\varepsilon_J}\right).\] This is the expected fraction of graphs below \((x,y)\) after a random vertical translation. Choose \(\varepsilon_J\) so that, at every proper crossing under consideration, the contribution of all graphs other than the one through the point differs from their unsmoothed count by at most \(1\). The choice is possible because there are finitely many crossings and all these other vertical distances are nonzero. Hence at a crossing on the \(i\)th graph in height order, \[ |r_J-i/M|\le 2/M. \tag{4}\] The choices can be made separately for all countably many windows.

For fixed \(x\), the function \(y\mapsto r_J(x,y)\) is continuous, strictly increasing, and has limits \(0\) and \(1\). Every level \(r_J=v\), where \(0<v<1\), is therefore a full continuous graph \(y=g_{J,v}(x)\). For \(x'>x\) the inequalities for the slopes of the original graphs give \[\ell_J(x'-x)\le g_{J,v}(x')-g_{J,v}(x) \le u_J(x'-x).\] For example, translating \((x,y)\) by \((h,u_Jh)\) can only increase \(r_J\); the upper inequality follows by applying this at a level point. The lower inequality is analogous.

Suppose \(A\) precedes the disjoint window \(B\). Then \(u_A<\ell_B\). Consequently the difference of any \(A\)-level graph and any \(B\)-level graph is strictly decreasing, with opposite infinite limits at the two ends of the real line. The graphs meet exactly once. Their intersection depends continuously on the two levels: bracket its \(x\)-coordinate on either side by strict inequalities, which persist under small changes of the levels, and then use continuity of a level graph. We have proved that \[ (r_A,r_B):\mathbb R^2\longrightarrow(0,1)^2 \quad\hbox{is a homeomorphism}. \tag{5}\] If \(C\) is disjoint from both \(A\) and \(B\), expressing \(r_C\) in these coordinates gives a function monotone in each coordinate. Indeed, along an \(A\)-level graph, \(r_B\) decreases strictly as \(x\) increases; along a \(B\)-level graph, \(r_A\) increases strictly. Compare the slope range of \(C\) with that of the level graph to determine the sign of \(r_C\). The two signs, in the order \((r_A,r_B)\), are \((+,-)\) when \(C<A\), \((+,+)\) when \(A<C<B\), and \((-,+)\) when \(B<C\).

Crossing density and variation

For two disjoint windows \(I,J\), sort their respective graph families pointwise into \(M\) ordered graphs. Sorting preserves continuity and the two bounds on chord slopes. Each pair of sorted graphs, one from each family, therefore meets at most once. A proper crossing of an \(I\)-edge and a \(J\)-edge determines a unique such pair of slots, and no two crossings determine the same pair. By (4), the pair \((r_I,r_J)\) at this crossing is within \(2/M\) in each coordinate of the corresponding grid point \((i/M,j/M)\). After giving every crossing mass \(M^{-2}\), every weak limit of the pair-coordinate projection is thus at most planar Lebesgue measure on \([0,1]^2\). One way to see the last assertion is to test a nonnegative continuous function: its integral is bounded by the full \(M\times M\) Riemann sum, up to its modulus of continuity at \(4/M\).

There is also a uniform bound on the variation of a rank coordinate along the edges: \[ \sum_e\operatorname{Var}_e(r_J)\le 2M. \tag{6}\] To prove it, compare one vertically translated convex graph with one chain of the concave partition of the full edge set. Their height difference is concave, so its positive set is an interval. The indicator of being above the translated graph has variation at most \(2\) along this chain. Averaging over the translations and the \(M\) convex graphs bounds the variation of \(r_J\) along a concave chain by \(2\). There are at most \(M\) concave chains. This proves the displayed bound, including tangencies, because the superlevel-set argument counts changes of sign rather than transverse intersections.

Enumerate the windows as \(J_1,J_2,\ldots\) and give the compact cube \[Z=[0,1]^{\mathbb N} \quad\hbox{the metric}\quad d(z,z')=\sum_{j\ge1}2^{-j}|z_{J_j}-z'_{J_j}|.\] Label every point \(q\) of the plane by \(z(q)=(r_J(q))_J\). For an edge \(e\), let \(\operatorname{osc}_e z\) be the diameter of its image in this metric. By (6) and summing the nonnegative series, \[\sum_e\operatorname{osc}_e z\le 2M.\] In particular, for each fixed \(\rho>0\) the number of edges whose label oscillation exceeds \(\rho\) is at most \(2M/\rho=o(E_*)\).

The limiting measures

Vertices, edges, and crossings require different normalizations. We attach the rank label \(z(q)\) to each vertex and crossing point; an edge \(e\) receives the label \((z(q_e),t_e)\), where \(q_e\) is its left endpoint and \(t_e\) its batch time. The following table defines the finite measures and names their weak limits:

Here \(E_*=Ra^2\) and \(M=aN\), and crossing measures are defined for disjoint windows \(I,J\). Each participating vertex is counted once within a window. Thus, for example, the full vertex and edge measures are \(N^{-1}\sum_{q\in P}\delta_{z(q)}\) and \(E_*^{-1}\sum_e\delta_{(z(q_e),t_e)}\). Compactness and bounded masses give a common weakly convergent subsequence for this countable collection of measures. In particular \(\mu\) and \(\nu\) are probability measures. Define the endpoint marginals and the total participating-vertex masses by \[s_J=\mu_J(Z),\qquad \lambda=\pi_{Z\,*}\nu,\qquad \lambda_J(F)=\nu(F\times J).\] The measures \(\lambda\) and \(\lambda_J\) count edge endpoints with edge weights, rather than counting distinct vertices. In particular, \(\lambda_J\) is additive over disjoint time windows, whereas the participating sets counted by \(\mu_J\) may overlap. We have \(\mu_J\le\mu\) and \(S_J/N\to s_J\). The time marginal of \(\nu\) is Lebesgue measure, since each batch has the same number \(a^2\) of edges and the batch times form a uniform grid. In particular every fixed window boundary is \(\nu\)-null. Restrictions to windows therefore converge weakly, and \(\lambda_J(Z)=|J|\). Disintegration on the compact metrizable spaces (Viana n.d., Example 2 and Theorem 3) supplies probability measures \(h_z\) on \([0,1]\), measurable in \(z\), such that \[ \lambda_J=h_z(J)\lambda. \tag{7}\] Equivalently, \(\lambda_J(F)=\int_F h_z(J)\,d\lambda(z)\) for every Borel \(F\subset Z\). Thus \(h_z\) is the conditional distribution of batch time under edge mass, given the endpoint rank label. On the \(\lambda\)-null set where a version has not been specified, choose any probability measure. Finally, the preceding grid argument gives \[ (z_I,z_J)_*\sigma_{IJ}\le\mathcal L^2\big|_{[0,1]^2}. \tag{8}\]

The crossing projection bound concerns \(\sigma_{IJ}\), whereas our eventual contradiction must control the edge mass \(\lambda\) using the participating-vertex measures \(\mu_J\). We next establish the relations between these measures. For any dyadic partition into windows of length \(\delta\), the finite activity-packing bound implies \[ \#\{J: |J|=\delta,\ s_J>u\}\le C u^{-4/3} \qquad(u>0). \tag{9}\] Indeed a window with \(S_J>uN\) has activity exceeding \(uN\), and these windows have disjoint step sets. Apply the uniform finite estimate and then take the limit for this finite collection of windows.

The compact labels now retain three useful features: two separated rank coordinates parametrize the plane; conditional edge activity has no time atoms; and every positive portion of activity is detected by a crossing measure with a bounded planar projection. These are the inputs to the local geometric argument.

Calculus for the limiting coordinates

We first record the two analytic facts needed below. Differentiability of coordinatewise monotone functions is classical (Chabrillac and Crouzeix 1987); the precise finite-dimensional statement is also given in (Borwein et al. 2004, Theorem 1(f)). We include the argument needed here. Monotonicity in each coordinate may have either prescribed sign; reflecting a coordinate reduces the first lemma to the nondecreasing case.

The next lemma concerns the entire set of differentiability points with singular derivative. This distinction matters because a crossing measure need not be absolutely continuous in the coordinates of the domain. The statement is the equal-dimensional critical-image estimate; a matching formulation appears in (Payne and Redaelli 2025, Appendix B, Corollary B.4). We give the covering proof for the precise hypotheses used here.

A positive part with independent gradients

Because \(h_z\) is a nonatomic probability, for almost every \(z\) it gives positive mass to two dyadic windows whose closures are disjoint and contained in \((0,1)\). There are only countably many pairs, so we can fix such windows \(K,K'\) for which \[E=\{z:h_z(K)>0,\ h_z(K')>0\}\] has positive \(\lambda\)-measure. Equation (12) for \(K'\) implies that \(\lambda|_E\) is absolutely continuous with respect to the sum of its crossing measures. We may further restrict \(E\) to a positive-measure set on which \[ \lambda|_E\ll\sigma_{AB} \quad\text{for some disjoint }A,B\subset K'. \tag{14}\] For completeness, form a finite measure \(\Sigma\) from the countable sum by assigning strictly positive weights to its summands. If \(g_{AB}=d\sigma_{AB}/d\Sigma\), the sets \(\{g_{AB}>0\}\) cover \(\Sigma\)-almost all points. One of them has positive \(\lambda|_E\)-measure; restriction to it proves (14). Thus the projection of \(\lambda|_E\) to \[p=(z_A,z_B)\in(0,1)^2\] is absolutely continuous with respect to planar Lebesgue measure. The boundary of the square has zero mass by the same projection bound.

For each \(C\subset K\), express the finite coordinate \(r_C\) as a function of \((r_A,r_B)\). These functions are bounded and coordinatewise monotone, with signs determined by the relative order of the windows. Extract a subsequence on a countable dense grid, simultaneously for all \(C\). The lower monotone extensions of the grid limits give Borel monotone functions \(f_C\). At every continuity point \(p\) of \(f_C\), squeezing between grid points below and above \(p\) shows convergence even along moving arguments \(p_m\to p\).

To apply this convergence to the endpoint measure, take \(z\in\operatorname{supp}\lambda\) with pair coordinate \(p\in(0,1)^2\). There are actual finite endpoint labels \(z_m\to z\) along a subsequence: every open neighborhood of \(z\) has positive limiting mass and therefore contains finite endpoint labels at all sufficiently late indices. Their pair coordinates tend to \(p\), so moving-argument convergence gives, whenever \(f_C\) is continuous at \(p\), \[ z_C=f_C(p). \tag{15}\] By Lemma 12 and the absolute continuity of the pair projection, we can discard a \(\lambda|_E\)-null set so that all these identities hold and all the \(f_C\) are differentiable at \(p\).

The fixed pair \(A,B\) supplies a coordinate chart in which every \(f_C\) is differentiable at the pair coordinate of each remaining label. We now use crossing measures from pairs \(C,D\) inside each positively active window \(J\subset K\) to find independent gradients. Those crossing measures are controlled in their own \((C,D)\) coordinates; the critical-image lemma connects this control to derivatives in the \((A,B)\) chart.

Allowed tangent directions

Fix a remaining label \(z\) and its pair coordinate \(p\). At small rank scales \(h\), the preceding convergence and differentiability have the following iterated consequence: for every fixed \(R<\infty\), \[ r_C=f_C(p)+h\nabla f_C(p)\cdot w+o(h), \qquad w=\frac{(r_A,r_B)-p}{h},\quad |w|\le R. \tag{16}\] Here first \(h\downarrow0\), and for each fixed \(h\) the configuration index is taken sufficiently large. The estimate is uniform on the displayed ball, simultaneously for any fixed finite collection of \(C\). Indeed, differentiate \(f_C\) at \(p\), then bracket the ball by a finite grid of continuity points with mesh \(o(h)\) and use monotonicity. Choosing the indices successively gives the estimate for all \(C\) along any sufficiently fast diagonal. No rate uniform in \(p\) is asserted.

Orient each physical sweep direction by increasing original horizontal coordinate. For \(t\in K^\circ\), forward displacements on a line of direction \(t\) have a common prescribed sign in each of the two rank coordinates. Let \(Q\) be the resulting closed signed quadrant. For each \(t\in K^\circ\), define \(D_p(t)\subset Q\cap S^1\) by the linear inequalities \[\begin{align*} \nabla f_C(p)\cdot d&\ge0 &&\text{if $C\subset K$ lies strictly before $t$},\\ \nabla f_C(p)\cdot d&\le0 &&\text{if $C\subset K$ lies strictly after $t$}. \end{align*}\] “Strictly” here requires a positive time gap. It is an intersection of closed halfplanes with the quadrant, restricted to the unit circle, so it is a closed angular interval when nonempty.

Any pair of forward-ordered points on a line of direction \(t\), with bounded zoom coordinates tending to distinct limits \(w,w'\), satisfies \[ \frac{w'-w}{|w'-w|}\in D_p(t). \tag{17}\] This follows from monotonicity of \(r_C\) along the line and (16). The base point and the line may vary with the configuration. Moreover, \(D_p(t)\) is nonempty. In each configuration follow the forward line through the physical preimage of \(p\) until its rank image first exits the zoom unit ball. This exit exists: the rank map is a homeomorphism onto the open square, and the preimage of a compact subset is compact. Along a sufficiently fast diagonal the exit points have a convergent subsequence, and their unit limiting displacement belongs to \(D_p(t)\).

The singleton times in this lemma may depend on \(z\). We also need one fixed triple for a common normalization of the configurations. For every remaining \(z\), nonatomicity and \(h_z(K)>0\) allow rational times \(t_1<t_2<t_3\) in \(K^\circ\) such that both \(h_z((t_1,t_2))\) and \(h_z((t_2,t_3))\) are positive. Countable selection fixes one triple on a positive \(\lambda\)-measure subset. A further countable selection fixes a dyadic \(K_0\) with closure in \((t_1,t_2)\) and \(h_z(K_0)>0\) throughout a positive-measure subset, again denoted \(E\). Thus \[\lambda_{K_0}(E)>0, \qquad D_p(t_1),\ D_p(t_2),\ D_p(t_3) \text{ are pairwise disjoint compact angular intervals.}\] All restrictions made here are restrictions of the original spatial measure \(\lambda\). Positive conditional time mass was used only in the stated measurable events; positive spatial mass follows from the countable selections. These conclusions supply the directional input for the local geometric argument.

Application to the rank coordinates

Fix a rank point \(p\) where all functions \(f_C\) are differentiable and where the directional conclusion already proved holds. Choose three times \(\tau_1,\tau_2,\tau_3\) whose allowed direction sets are singletons and are pairwise projectively distinct. Let their unit directions be \(d_1,d_2,d_3\). Fix an invertible matrix \(B\) carrying \([d_1],[d_2],[d_3]\) to \([v_1],[v_2],[v_3]\).

Consider any radii \(h_j\downarrow0\) and indices tending sufficiently fast that, on every bounded set of \(w\) and for every fixed \(C\), \[ r_{C,j}(p+h_jw)=f_C(p)+h_j\nabla f_C(p)\cdot w+o(h_j). \tag{18}\] Here \(r_{C,j}\) denotes the \(C\) coordinate as a function of the pair of rank coordinates, and the error is uniform on the bounded set. This diagonal condition follows from monotone squeezing at continuity points and differentiability at \(p\). It asserts no uniform rate in the configuration index.

Normalize the original Euclidean plane linearly so its three \(\tau_i\) directions become \([v_i]\), translate the preimage of \(p\) to \(0\), and scale the whole plane so the image of \(v_1\) under the rank zoom \(B(r-p)/h_j\) has norm one. Such a scale exists: on the chosen horizontal ray the rank zoom is continuous, starts at zero, and exits every fixed ball contained in its expanding target domain. Let \(F_j\) be this map from the normalized Euclidean plane to rank zoom coordinates.

The first hypothesis of Lemma 16 holds with \(P=B^{-1}\), by the two original rank-coordinate monotonicities; passing to a subsequence fixes any orientation signs. Its second hypothesis follows from (18): every bounded limiting displacement on a \(\tau_i\) line satisfies all its directional sign constraints, so it is parallel to \(B d_i\), whether or not its base point moves. The target domains exhaust the plane since \(p\) is interior to the rank square. The lemma therefore applies. In this normalization the zoom and its inverse converge locally uniformly to a nonsingular linear map; with the stated choice they converge to \(\sigma I\).

We must compare this point-dependent normalization with the common normalization based on three fixed times \(t_1<t_2<t_3\): in each configuration a linear map sends their projective directions to a prescribed fixed triple. Let \(L_j\) map the open rank square to this common normalized Euclidean plane, by inverting the rank map and applying that linear map. At our point their allowed direction sets \(D_p(t_i)\) are compact and pairwise disjoint. Let \(\xi_{i,j}\) be their projective directions in the \(\tau\)-normalized Euclidean plane. After any further subsequence these directions have limits. Testing a unit segment through the origin in direction \(\xi_{i,j}\) in the uniformly convergent maps shows that its limiting image direction, after undoing \(B\), belongs to the projectivization of \(D_p(t_i)\). Equivalently, orient the tested segment in the original forward direction to obtain an oriented limit in \(D_p(t_i)\). Thus the limiting directions lie in three fixed, pairwise disjoint compact subsets of the projective line. Their separation is bounded below by a positive number depending only on \(p\) and the two fixed triples, independently of this zoom sequence.

Let \(A_j\) convert the \(\tau\) normalization to the common normalization, which sends the \(t_i\) directions to a prescribed fixed triple. These matrices have bounded condition number. Indeed normalize \(\|A_j\|=1\) and suppose a limit were singular. At most one of three separated limiting input directions could be its kernel, so two others would have the same limiting output direction. This contradicts the two corresponding distinct fixed output directions. Compactness gives a bound depending only on the separation and the fixed target triple.

It follows that for every diagonal satisfying (18), after translations, positive scalar rescalings and a subsequence, the common-coordinate maps \[w\longmapsto L_j(p+h_jw)-L_j(p)\] converge locally uniformly to an invertible linear map of condition number at most \(K_p<\infty\). Indeed the normalized limit is \(\sigma A B\), with \(A\) a nonsingular scalar-normalized limit of \(A_j\); the bound includes the fixed condition number of \(B\).

Define \[U_j(p,h)=\max_{|u-p|=h}|L_j(u)-L_j(p)|, \qquad V_j(p,h)=\min_{|u-p|=h}|L_j(u)-L_j(p)|.\] Choose \(C_p>K_p\). For each integer \(T\ge2\), there exists \(h_{p,T}>0\) such that for every fixed \(0<h<h_{p,T}\) and every sufficiently late configuration \(j\), \[ V_j(p,h/T)\ge\frac{U_j(p,h)}{C_p T}, \qquad U_j(p,h/T)\le\frac{C_p V_j(p,h)}{T}. \tag{19}\] If either eventual comparison failed for arbitrarily small fixed radii, choose radii tending to zero and failing indices arbitrarily late, late enough also to satisfy (18). Pass to the just-established linear limit. On the two circles its radial maxima and minima have ratios \(T\kappa\) and \(\kappa/T\), respectively, with \(\kappa\le K_p<C_p\), contradicting failure. This proves (19) in the order stated: first the fixed radius, then the configuration index.

Planar \(k\)-sets and straight-line levels

We finish by deriving the rank-sensitive consequence stated in the introduction. The local ranks created by a shallow cutting can vary from cell to cell, which is why the uniform sweep theorem was needed.