1 Introduction
Let P be a finite set of n points in the plane, with no three collinear, where n is even. A pair of points is a halving pair if its line leaves exactly (n-2)/2 other points in each open halfplane. Write h(P) for the number of unordered halving pairs. Because no three points are collinear, distinct pairs determine distinct lines; thus this convention also counts halving lines.
Theorem 1.1. There exist absolute constants \varepsilon>0, C<\infty, and n_0 such that, for every even n\ge n_0 and every n-point set P\subset\mathbb R^2 with no three collinear,
The improvement is in the exponent and is uniform over all configurations. The proof is nonquantitative: it supplies neither a numerical value of \varepsilon nor effective values of C and n_0.
1.1 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 [8, 10]. Pach, Steiger and Szemerédi improved the upper bound by an iterated-logarithm factor [13]. 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 [7]. 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 [8]. Tóth obtained n\exp(\Omega(\sqrt{\log n})) halving pairs, and Nivasch subsequently simplified the construction and improved its exponential constant [11, 20]. 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 [3].
A related route through measures was developed by Pinchasi [16]. 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.
1.2 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.
Theorem 1.2 (Uniform bound over all ranks). There are absolute constants \varepsilon>0 and C<\infty such that for every integer N\ge1, every generic N-point planar configuration P, and every integer 0\le k\le N,
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.
Corollary 1.3 (Planar k-sets and straight-line levels). There are absolute constants \varepsilon_0>0 and C_0<\infty such that, for every integer n\ge2 and every integer 1\le k\le n/2, the number of k-sets of any n-point set Q\subset\mathbb R^2 with no three collinear is at most
The same bound holds for \operatorname{comp}(\Lambda_k(\mathcal L)) for any arrangement \mathcal L of n nonvertical straight lines with no parallel pair and no three concurrent.
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.
1.3 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.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.
Background. We use weak compactness and regularity of finite Borel measures on compact metric spaces, the Radon–Nikodym and Lebesgue decomposition theorems and finite-measure differentiation [19, Chapter 1, Section 3], almost-everywhere differentiability of scalar Lipschitz functions, and planar separation by a Jordan curve. The conditional-measure and Lipschitz-differentiability statements are specified at their applications. The crossing, monotone-coordinate, critical-image, three-foliation, and boundary estimates needed for the new packing argument are proved in the paper.
2 Sweeps, activity, and exchange graphs
The chain and crossing mechanism below is the one underlying Dey’s bound [7]. We first convert intervals containing many participating points into straight-line graphs with controlled crossings. This gives the classical exponent 4/3 and isolates the packing estimate that must be improved.
We first justify the genericity convention of the introduction. The additional conditions on coordinates, slopes, and proper segment intersections can be achieved by an arbitrarily small perturbation. Indeed, the signs of the finitely many nonzero oriented areas of triples are unchanged by a sufficiently small perturbation. Consequently every pair has exactly the same points on its two sides, and in particular the halving pairs are preserved. The additional conditions exclude finitely many proper algebraic sets of perturbations.
Write P=\{(x_i,y_i):1\le i\le N\} and fix a rank k, with 0\le k\le N. At a slope s that is not a determined slope, let M_k(s) be the set of the k smallest values of y_i-sx_i. Choose one representative slope in each interval between consecutive determined slopes, including the two unbounded intervals. These are the states; adjacent states form a step. A step either leaves M_k unchanged or replaces one point by one other point. The latter kind of step is a switch. An interval of states includes its endpoints, and its step set consists of the intervening steps. Its activity is the number of distinct points whose membership in M_k changes at one of those steps. Thus activity counts points, rather than switches. For two sets of size k put
Activity records membership changes throughout the interval, whereas d(M,M') records only the difference of its endpoint sets. This is a metric, and one step changes distance from a fixed state by at most one. At middle rank, the same endpoint-set distance occurs in Pinchasi’s study of slope-ordered balanced cuts and measure concentration [16]; the activity reduction below also handles points that return to their initial membership.
At a switch the gained point has larger first coordinate than the lost point: the difference of their two projections changes sign as s increases. The sum of first coordinates in M_k therefore increases strictly at every switch. In particular an interval of positive activity has different endpoint sets.
Our main intermediate result strengthens the classical crossing bound for collections of disjoint sweep intervals. Its quantifier is uniform in both the rank and the activity threshold.
Theorem 2.1 (Uniform activity packing). For every \xi>0 there is Q_\xi<\infty such that, for every generic N-point configuration, every rank, and every integer 1\le b\le N with N/b\ge Q_\xi, any collection of intervals with disjoint step sets and activity at least b has at most \xi(N/b)^{4/3} members.
We first establish the finite reductions and the corresponding O((N/b)^{4/3}) bound. Sections 3–7 prove the improvement to the displayed arbitrarily small constant.
Lemma 2.2 (Activity and endpoint distance). Fix a generic N-point set and a rank k. For an integer b\ge4, any collection of intervals of activity at least b can be divided into two classes. At rank k+\lfloor b/4\rfloor the intervals in the first class have endpoint distance at least \lfloor b/4\rfloor; at rank k-\lfloor b/4\rfloor the intervals in the second class do so. Each rank used by a nonempty class is feasible. For 1\le b<4, the original rank already gives endpoint distance at least one.
Proof. Set c=\lfloor b/4\rfloor. Classify an interval according to whether at least b/2 of its active points were unmarked initially; put all remaining intervals in the second class. In the first case let E be the initially marked set at rank k+c. At most c of the initially unmarked active points lie in E, so at least \lceil b/2\rceil-c\ge c of them lie outside E.
Take such a point u. At some state it enters rank k, and is then below at least c+1 of the k+c points of E in projection order. Initially it was above all of E. For each of those c+1 points the projection difference is affine in the slope, so the new comparison persists to the final state. Let E' be the final rank-(k+c) set. If at least c of the specified points outside E lie in E', then |E'\setminus E|\ge c. Otherwise one of them, say u, is outside E'. All c+1 points of E that remain above u are then outside E', so again the endpoint distance is at least c. There were at least \lceil b/2\rceil initially unmarked points, which also proves k+c\le N.
The other class has at least b/2 initially marked active points. Apply the preceding argument to the complementary marks and the negated projections; enlarging the complementary rank by c is the same as reducing the original rank by c. Its feasibility follows in the same way. The case b<4 follows from the strict increase of the sum of first coordinates at switches.
Lemma 2.3 (Greedy batches). Fix a rank and an integer d\ge1, and put a=\lceil d/2\rceil. Starting at the first state, end a batch at the first subsequent state at distance a from its start, and repeat while possible. If R complete batches are obtained, every collection of intervals with disjoint step sets and endpoint distance at least d has at most R members.
Proof. Distances change by at most one at a step, so every completed batch has distance exactly a. If an interval contains no batch end strictly after its start, both its endpoints are at distance at most a-1 from the same preceding batch start. Their mutual distance is at most 2(a-1)<d, a contradiction. This applies also in the final unfinished batch. Assign to each interval a batch end strictly after its start and at or before its end. Disjoint step sets cannot receive the same batch end.
Now consider any consecutive batches of endpoint distance a. In a batch let L be the a points lost between its endpoint states and G the a points gained. Draw all a^2 segments from L to G. Every segment points strictly to the right, and its slope lies strictly between the two state slopes of the batch. Indeed, for u\in L and v\in G, their projection order is reversed between the two states. A pair cannot occur in two batches because its determined slope would have to belong to two disjoint open slope intervals. The resulting exchange graph is therefore simple.
Lemma 2.4 (Two chain partitions). For a consecutive window of batches, let S be the number of distinct endpoints of its exchange edges. Those edges partition into at most aS convex polygonal chains, and also into at most aS concave polygonal chains. The number of properly crossing edge pairs is at most 2a^2S^2.
Proof. Decompose each complete bipartite exchange into a perfect matchings, and number the matchings from 1 to a. For one matching number, place a token at each marked point at the start of the window. In every batch move the token at each lost point to its matched gained point, leaving all other tokens in place. Along a token’s moving segments the first coordinate increases, and segment slopes increase strictly from batch to batch. Its nonempty trajectory is a convex polygonal chain. A token that ever moves starts at an endpoint in the window: its first move otherwise could not occur. Thus there are at most S nonempty chains for each matching number.
Instead place tokens at the unmarked points and move them from gained to lost points along the same matchings. They move left as time increases. Reading a trajectory from left to right reverses the batch order, so its slopes decrease. This gives the concave partition, again with at most aS chains.
On their common horizontal domain the difference of a convex chain and a concave chain is a convex piecewise affine function. It has at most two sign-changing zeros, and hence the chains have at most two proper transverse intersections in edge interiors. Shared segments do not count as proper crossings and do not increase this bound. Assign one edge of each crossing pair to its convex chain and the other to its concave chain. The genericity assumptions exclude multiple proper crossings at one point. Summing over chain pairs proves the stated bound.
The classical crossing lemma is due independently to Ajtai, Chvátal, Newborn and Szemerédi, and to Leighton [2, 9]. The asymmetric sampling argument below is the imbalanced bipartite crossing argument of Pach, Solymosi and Tardos [12, Lemmas 2.1–2.2]; we include the reduction to designated endpoints and the constants needed here. We need a version of the crossing estimate that also controls edges whose endpoint lies in a prescribed small set. In the next lemma \operatorname{cr}(G) denotes the number of properly crossing edge pairs in the given drawing, not the minimum over drawings.
Lemma 2.5 (Crossings with designated endpoints). Let a simple graph be drawn with straight segments on v distinct points, with no vertex in an edge interior and no crossings of incident edges. Suppose every edge has an endpoint in a specified set of at most m\le v vertices. If the graph has e edges, then
In particular, if e\ge24v, then e^3\le2304\,mv\,\operatorname{cr}(G).
Proof. The assertion is immediate if e<24v or e=0. Select each designated vertex independently with probability 1/2, put these selected vertices on one side, and put all other vertices on the other side. Every edge crosses this cut with probability 1/2. Some resulting bipartite subgraph therefore has e_0\ge e/2 edges, with side sizes at most m and v.
Retain vertices on its two sides independently with probabilities
respectively. Both probabilities lie in [0,1]. Any graph in this drawing satisfies e'\le3v'+\operatorname{cr}': deleting at most one edge for each crossing leaves a simple plane graph. Taking expectations gives
The factor p^2q^2 is valid because crossing edges have four distinct endpoints. Substitution yields e_0^3\le288mv\operatorname{cr}(G), and e_0\ge e/2 proves the dense assertion. The additional term 24^3v^3 covers the remaining case.
For R consecutive batches on N points the graph has Ra^2 edges and at most 2a^2N^2 crossing pairs. Applying Lemma 2.5 with m=v\le N, and separating the sparse case, gives
Here a\ge1 and N\ge1, so the first summand is absorbed by the second. Lemmas 2.2 and 2.3 now show that the number of intervals with disjoint step sets and activity at least b is O((N/b)^{4/3}), uniformly in the rank. The reductions also show that a uniform improvement to o((N/a)^{4/3}) for consecutive distance-a batches, as N/a\to\infty, gives the same little-o improvement for activity packing. There are only two rank classes, and for b\ge4 their batch parameter obeys b/16\le a\le b/4; for b<4 it is a=1.
We record also the localized bound to be used below. If a window has S distinct endpoints and e_F of its edges have their left endpoint among a specified m of those endpoints, then
Indeed this subgraph has at most S vertices and inherits the crossing bound from Lemma 2.4. The second term explicitly retains the sparse case; it may only be discarded after an appropriate limiting normalization.
The remainder of Sections 3–7 proves Theorem 2.1. The finite reductions show that a failure produces a sequence of consecutive distance-a batches with N/a\to\infty and R\asymp(N/a)^{4/3}. We will derive a contradiction from such a sequence. Afterward Section 8 converts this uniform statement into the power saving of Theorem 1.1.
3 Rank coordinates and limiting measures
We now suppose, for a contradiction, that there is a sequence of batch systems for which
Here each of the R batches exchanges a lost points for a gained points, and contributes the a^2 rightward edges between them. Write
Thus E_*^3\asymp a^2N^4 and E_*/M\to\infty. The constants below may depend on the two constants in the displayed comparison for R. Our objective in this section is to assign compact labels to points so that edge mass is controlled by vertex mass, and every positive portion of edge mass sees crossings between different time windows.
Give batch i the time (i-1/2)/R. A window is a dyadic subinterval of [0,1], with the half-open convention except at the right endpoint 1. Its edges are those of its batches. The consecutive batches in a nonempty window have a slope span, from the state just before its first batch to the state just after its last batch. Disjoint windows have slope spans with disjoint interiors. Every edge slope is strictly inside its batch span. Each fixed window is nonempty eventually. For a fixed time t\in(0,1), choose batch i=1+\lfloor Rt\rfloor and take the arithmetic mean of its two endpoint-state slopes. A line of direction t means a line parallel to this configuration-dependent slope. The half-open convention fixes the choice at cell boundaries. For fixed times and windows separated by positive gaps, these directions have the same strict order as their times for all sufficiently late configurations.
Let S_J denote the number of distinct endpoints of the exchange edges in J. These are exactly the points whose membership changes between the endpoint states of at least one batch in J. A point that changes membership within a batch and returns before its end contributes to the sweep activity but need not contribute to S_J. Thus S_J is at most the activity of the full sweep interval covered by J. The finite estimates proved above give
They also give convex and concave partitions of the full edge set into at most M chains; the edges of a window have such partitions into at most aS_J chains.
3.1 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
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 ith graph in height order,
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
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
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.
3.2 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 (3.2), 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:
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
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 (3.4) and summing the nonnegative series,
In particular, for each fixed \rho>0 the number of edges whose label oscillation exceeds \rho is at most 2M/\rho=o(E_*).
3.3 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:
| Object | Weight of one finite object | Weak limit |
| Vertex | N^{-1} | \mu on Z |
| Participating vertex in J | N^{-1} | \mu_J on Z |
| Edge with its batch time | E_*^{-1} | \nu on Z\times[0,1] |
| Crossing between I and J | M^{-2} | \sigma_{IJ} on Z |
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
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 [21, Example 2 and Theorem 3] supplies probability measures h_z on [0,1], measurable in z, such that
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
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
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.
Lemma 3.1 (Edge mass and vertex mass). For every window J and every Borel set F\subset Z,
In particular \lambda\ll\mu. The same estimate holds if additional labels in a compact metrizable space are attached to vertices, inherited by their edge endpoints, and a further weak limit is taken.
Proof. For a set U of labels in a finite configuration, take the edges in J whose left endpoint belongs to U. Write e(U) for their number and m(U) for their number of distinct left endpoints. The graph has at most S_J vertices, and all its edges have a designated endpoint in a set of m(U) vertices. The designated-endpoint crossing inequality, with its sparse-graph alternative, and (3.1) give
After division by E_*^3\asymp a^2N^4, the last term tends to zero, since it is at most C/(a^2N). Also m(U)/N is at most the participating-vertex measure of U.
For a compact F, use its open \rho-neighborhood as U and bound its vertex measure by that of the closed 2\rho-neighborhood. Weak convergence and the open-set and closed-set inequalities give
Let \rho\downarrow0. Inner regularity of \lambda_J then extends the estimate from compact to all Borel sets. Take J=[0,1] to obtain absolute continuity. The finite argument makes no use of the nature of the labels, proving the last assertion as well.
Lemma 3.2 (No atoms in conditional time). For \lambda-almost every z, the probability measure h_z is nonatomic.
Proof. Fix \beta>0 and a dyadic partition of mesh \delta. Put A_J=\{z:h_z(J)>\beta\}. At each z at most 1/\beta of these sets occur. Thus \sum_J\mu_J(A_J)\le1/\beta. For M_0\ge1, the windows with s_J>M_0\delta^{3/4} contribute at most C M_0^{-4/3} to \sum_J\lambda_J(A_J), by (3.7) and \lambda_J(Z)=\delta. The remaining windows contribute, by (3.8) and Hölder’s inequality, at most
First let \delta\downarrow0, then M_0\to\infty. If h_z has an atom of mass greater than \beta, the member of every partition containing that atom contributes at least its mass to \sum_Jh_z(J)\mathbf1_{A_J}(z). Fatou’s lemma therefore shows that such z form a \lambda-null set. A countable sequence of positive \beta tending to zero proves the claim.
Lemma 3.3 (Edge mass sees crossings). For every window K,
where the sum specifies null sets. Thus, if a Borel set F\subset Z is null for every \sigma_{IJ} with I,J\subset K disjoint windows, then \lambda_K(F)=0.
Proof. By inner regularity it suffices to consider a compact set F that is null for every crossing measure on the right of (3.9). Fix a dyadic resolution \delta subdividing K, and discard windows with s_J>\delta^{2/3}. Their number is at most C\delta^{-8/9}, so the limiting edge mass lost is at most C\delta^{1/9}. In the remaining windows keep edges whose left-endpoint label lies in the open \rho-neighborhood of F and whose label oscillation is at most \rho. For fixed \delta,\rho>0, the oscillation condition costs o(E_*) edges. If e_{\delta,\rho} is the total number retained, weak convergence consequently gives
A crossing between retained edges from different windows has label in the closed 2\rho-neighborhood of F. For this fixed finite partition, its normalized limsup is therefore bounded by
where each unordered pair is counted once. This tends to zero as \rho\downarrow0. Crossings within one retained window are bounded by (3.1); after division by M^2 their total limsup is at most
The ordinary crossing inequality, including its sparse alternative, reads e_{\delta,\rho}^3\le C N^2\operatorname{cr}+C N^3. Divide by E_*^3\asymp a^2N^4, take the configuration limit, and then let \rho\downarrow0. It follows that
Finally let \delta\downarrow0. This gives \lambda_K(F)=0, as required. Equivalently, \lambda_K is absolutely continuous with respect to any countable mixture of the crossing measures in the statement whose coefficients are all positive and whose total mass is finite.
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.
4 Differentiable coordinates and transverse directions
We now convert the crossing measures into local geometric information. The input is the countable family \mathcal D of dyadic time windows, the edge endpoint marginal \lambda on the rank cube Z, its conditional time probabilities h_z, and the crossing measures \sigma_{CD} constructed above. We use three established facts: h_z is nonatomic for \lambda-almost every z;
and the (C,D)-coordinate projection of \sigma_{CD} is dominated by planar Lebesgue measure. The sum in (4.1) specifies null sets; it may equivalently be replaced by a finite measure formed from a countable sum with strictly positive weights. Our objective is to find a positive part of \lambda on which three different sweep directions have three different tangent directions.
4.1 Calculus for the limiting coordinates
We first record the two analytic facts needed below. Differentiability of coordinatewise monotone functions is classical [6]; the precise finite-dimensional statement is also given in [5, 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.
Lemma 4.1. A bounded Borel function on an open rectangle in \mathbb R^2 that is monotone in each coordinate is Fréchet differentiable almost everywhere with respect to planar Lebesgue measure.
Proof. It suffices to work in a compact subrectangle and assume that both monotonicities are nondecreasing. Slice monotonicity shows that the distributional derivatives D_1f,D_2f are locally finite positive measures. Put \nu=D_1f+D_2f and Q_r(x)=x+[-r,r]^2. For a square lying sufficiently far inside the domain, monotonicity and integration over x+[-2r,-r]^2 give
Indeed, compare every point u of that lower square with u+(3r,3r). The difference of their function values is at least the middle difference in (4.2). Integrating the horizontal increment and then the vertical increment by slices bounds the resulting integral by r\nu(Q_{3r}(x)); the lower square has area r^2.
The upper area density of \nu is finite at almost every x. Consequently, at almost every x there are M_x,r_x>0 such that |f(y)-f(x)|\le M_x|y-x| whenever |y-x|<r_x. These points are covered by countably many measurable sets E_m on which the restriction of f is Lipschitz. For example, on a fixed bounded subrectangle one may impose a uniform bound on the corner differences in (4.2) for every rational 0<r<1/m; boundedness deals with pairs at distance at least 1/m. Extend f|_{E_m} to a Lipschitz function g_m on the plane.
By Rademacher’s theorem [17], in the form stated in [19, Chapter 2, Theorem 1.4], the Lipschitz extension g_m is differentiable almost everywhere. Thus, at almost every point x\in E_m, the set E_m has density one and g_m is differentiable. Its first-order expansion also holds for f at arbitrary nearby points. To see this, write y=x+v and choose y^-,y^+\in E_m with
Such points exist by density one: a missing box of side comparable to |v| in either prescribed corner would contradict density, and the relative box size can tend to zero. Monotonicity squeezes f(y) between g_m(y^-) and g_m(y^+), giving f(x+v)=f(x)+Dg_m(x)v+o(|v|). Countably many sets E_m cover almost all points, proving the claim.
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 [15, Appendix B, Corollary B.4]. We give the covering proof for the precise hypotheses used here.
Lemma 4.2. Let F:\Omega\to\mathbb R^2 be any map, where \Omega\subset\mathbb R^2 is open. The image of the set of points at which F is Fréchet differentiable and \operatorname{rank}DF<2 has planar outer measure zero.
Proof. Restrict that set to S\subset B(0,R) where \|DF(x)\|\le M. Fix \varepsilon>0. For each x\in S choose arbitrarily small radii r<1 such that B(x,5r)\subset\Omega and
The elementary 5r covering lemma gives disjoint balls B(x_i,r_i) whose fivefold enlargements cover S. Since their centers lie in B(0,R), we have \sum_i r_i^2\le (R+1)^2. The set F(B(x_i,5r_i)) lies in the 5\varepsilon r_i neighborhood of a segment of length at most 10Mr_i. Its outer area is therefore at most C(M\varepsilon+\varepsilon^2)r_i^2. Summing these covers and letting \varepsilon\downarrow0 proves that F(S) is null. A countable union over R,M completes the proof.
4.2 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
has positive \lambda-measure. Equation (4.1) 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
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 (4.3). Thus the projection of \lambda|_E to
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,
By Lemma 4.1 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.
Lemma 4.3. After discarding a further \lambda|_E-null set, every label z\in E has the following property: if J\subset K is dyadic and h_z(J)>0, then some disjoint dyadic C,D\subset J satisfy
Proof. Fix J. Let B_J\subset E be the labels with h_z(J)>0 for which every such determinant vanishes. For each disjoint C,D\subset J, Lemma 4.2, applied to F=(f_C,f_D), gives a Borel planar null set containing
By (4.4), the (C,D) projection of B_J lies in that null set. Projection domination therefore gives \sigma_{CD}(B_J)=0. Equation (4.1) implies \lambda_J(B_J)=0. Since \lambda_J(B_J)=\int_{B_J}h_z(J)\,d\lambda(z) and h_z(J)>0 on B_J, we get \lambda(B_J)=0. Discard these null sets for all countably many J.
4.3 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,
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
“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
This follows from monotonicity of r_C along the line and (4.5). 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).
Lemma 4.4. If s<t lie in K^\circ and h_z((s,t))>0, then D_p(s)\cap D_p(t)=\varnothing. There are three times \tau_1<\tau_2<\tau_3 in K^\circ for which these intervals are singletons with distinct projective directions.
Proof. Choose a dyadic J whose closure lies in (s,t) and for which h_z(J)>0. Lemma 4.3 provides disjoint C,D\subset J with independent gradients. A vector belonging to both D_p(s) and D_p(t) would have zero scalar product with both gradients, and hence be zero, contrary to unit length.
Consider the support of the nonatomic measure h_z|_{K^\circ}. Remove the endpoints of its complementary intervals and the endpoints of K. Only countably many points are removed, and any two distinct remaining support points have positive measure strictly between them. Their intervals D_p(t) are consequently pairwise disjoint. At most countably many disjoint angular intervals can have positive length, since each contains a different rational angle. Removing those times still leaves full h_z|_K-measure. Three remaining times give the claim. All directions lie in the same quadrant, so distinct unit directions are also projectively distinct.
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
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.
5 Three transverse foliations determine the zoom
Exact preservation of three transverse families of parallel lines is an affine rigidity phenomenon; see Artstein-Avidan and Slomka [4]. We need a compactness statement that also rules out collapse before a limit map has been obtained. The following elementary lemma prevents a change of coordinates from collapsing at the scale under consideration. Its monotonicity hypothesis is imposed before any fixed linear change of the target coordinates. For a vector v, write [v] for its unoriented line through the origin.
Lemma 5.1 (Three-foliation compactness). Let \Omega_j\subset\mathbb R^2 be open sets containing every compact subset of \mathbb R^2 for all sufficiently large j. Let F_j:\mathbb R^2\longrightarrow\Omega_j be homeomorphisms. Put v_1=(1,0), v_2=(0,1) and v_3=(1,1). Suppose the following hold.
- 1.
There is a fixed invertible matrix P such that each coordinate of P F_j is monotone on each line parallel to v_i. For each i, the two monotonicity signs are independent of the line and of j.
- 2.
Along every subsequence, if x_j,y_j lie on one line parallel to v_i and F_j(x_j)\to a, F_j(y_j)\to b, then b-a\in\mathbb R v_i. The points and their common line may depend on j.
- 3.
F_j(0)=0 and |F_j(v_1)|=1.
After passage to a subsequence there is \sigma\in\{-1,1\} such that F_j\to \sigma\operatorname{id} uniformly on compact sets. The inverse maps converge to \sigma\operatorname{id} uniformly on compact sets as well.
Proof. We first control images of entire lines and intersections between families. Those intersections then determine the map on rational grids; coordinate monotonicity will extend this control to compact sets. The final step will control the inverse maps.
To begin, we show that entire line images, including lines with moving base points, converge to the prescribed target lines. Fix a family i and points x_j with a_j=F_j(x_j)\to a. Orient the source lines in the direction v_i. Their forward target displacements belong to a fixed closed pointed cone Q_i, the inverse under P of the signed coordinate quadrant specified by the first hypothesis. Choose a linear functional \ell_i strictly positive on Q_i\setminus\{0\}. There is M_i<\infty such that
Consequently s=\ell_i(F_j(x)-a_j) is a strictly increasing continuous parameter on the image of this oriented source line: injectivity rules out equality at two points. In this parameter its image \gamma_j is M_i-Lipschitz.
The parameter intervals exhaust \mathbb R. Indeed, for any fixed R, a ball containing all points at distance at most M_iR+1 from a_j lies in \Omega_j for large j. The preimage of its closure is compact, so each source ray eventually leaves that ball. The cone inequality forces its parameter to exceed R in the positive direction or to be less than -R in the negative direction. This proves the claim without any control of the Euclidean locations x_j.
At parameter s=1, a convergent subsequence gives a nonzero vector in Q_i\cap\mathbb R v_i: its \ell_i value is one. Thus this intersection contains a ray, and pointedness makes the ray unique. Compactness of equi-Lipschitz curves and the second hypothesis now imply
where d_i is the unit vector on \mathbb R v_i belonging to Q_i. There is exactly one such ray; \ell_i(d_i)>0. The formula also shows that the limit is unique, so no additional subsequence is needed for this assertion. In particular the line image traces the entire limiting line in both directions.
It follows that intersections of two different families converge. More precisely, let two source lines of types i\ne k have base images tending to a and b. The two limiting lines intersect at a unique point c. In a small parallelogram around c with sides parallel to these limiting directions, the preceding parameterized convergence produces arcs close to the two transverse diameters and joining their respective opposite sides. They intersect by planar separation, in the opposite-sides form of [14, Lemma 2.11]. The source lines have exactly one intersection, and their images do also because F_j is a homeomorphism. Hence this unique intersection is inside every sufficiently small such parallelogram eventually, proving convergence to c. The argument allows a=b; transversality concerns the two line types, not the two base points.
We have controlled intersections even when their base points move. We next use those intersections to determine the scale at every rational point, starting from the normalized pair 0,v_1.
Pass to a subsequence so F_j(v_1) converges. Its limit is \sigma v_1 with \sigma=\pm1 by the second and third hypotheses. Starting with 0,v_1, intersections of horizontal, vertical and slope-one lines generate the integer lattice. For example the diagonal through 0 meets the vertical through v_1 at (1,1); its horizontal meets the vertical through 0 at (0,1). The diagonal through v_1 meets that vertical at (0,-1). These operations and their reverses give each integer step and then every lattice intersection; Figure 1 shows the first steps. Intersection convergence proves F_j(z)\to\sigma z at all integer lattice points.
Figure 1: The source-plane intersection construction using horizontal, vertical and slope-one lines. The diagonal through 0 meets the vertical through v_1 at v_3; its horizontal gives v_2. The diagonal through v_1 meets the vertical through 0 at -v_2. Convergence of the image intersections is proved in the text.
Fix m\ge1. By the original two coordinate monotonicities, P F_j(v_1/m) is in the coordinate rectangle with vertices 0 and P F_j(v_1), so it is bounded. Every subsequential limit is b v_1 by the second hypothesis. Apply the same finite intersection construction with seed v_1/m in place of v_1. It constructs v_1 after m additions, and intersection convergence shows that its limiting image is mbv_1. Thus mb=\sigma. This argument is valid even if one initially supposes b=0, since every intersection is between two different line types. Therefore F_j(v_1/m)\to\sigma v_1/m without a noncollapse assumption. Repeating the grid construction proves convergence on (m^{-1}\mathbb Z)^2, and hence at every rational point.
Finally squeeze each coordinate of P F_j between the appropriate corners of a rational grid cell. The signs can differ between the two coordinates and the two source axes; choose the lower and upper corners for each coordinate separately. The limiting corner values are those of \sigma P x, whose oscillation on a cell is bounded by a constant times its mesh. A finite grid covering a compact set therefore proves uniform convergence there. This uses monotonicity of P F_j, not an unjustified monotonicity of F_j.
For inverse convergence, choose a circle sufficiently large to contain a given compact target set with positive margin. Uniform convergence on that circle and the Jordan curve theorem (see [18]) show that its image encloses the target set for large j; this image bounds the image of the source disk. The inverse images of the target set are thus uniformly bounded. Uniform convergence of F_j on that disk gives uniform convergence of the inverses.
5.1 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,
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 5.1 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 (5.1): 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 (5.1), after translations, positive scalar rescalings and a subsequence, the common-coordinate maps
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
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,
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 (5.1). 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 (5.2) in the order stated: first the fixed radius, then the configuration index.
6 A spatial measure with dimension greater than seven quarters
The boundary argument will count participating vertices, so it needs a strip estimate for vertex mass while retaining a positive amount of edge mass. We now construct a single Euclidean limit with these two properties. The metric estimate from the preceding section concerns one fixed rank point and radius at a time. A Hausdorff limit of graphs will allow us to use it with configuration thresholds that still depend on the point and radius.
Write D=(0,1)^2, and let \pi:Z\to[0,1]^2 be the projection onto the rank coordinates (z_A,z_B). Denote the inverse rank maps, in the common Euclidean normalization, by L_n:D\to\mathbb R^2. These are homeomorphisms. For \overline B(p,h)\subset D, put
The input from the preceding section has the following exact quantifiers. For each selected p, there is C_p<\infty such that, for every integer T\ge2, all sufficiently small fixed h>0 satisfy, eventually in n,
The constant C_p is independent of T. The allowed radii may depend on p,T, and the eventual index may depend on p,T,h.
We use the positive good part already selected above: a Borel set E\subset Z with \lambda_{K_0}(E)>0, whose restricted endpoint measure has absolutely continuous pair-coordinate projection, and for which (6.1) holds at every p\in\pi(E) after deleting a null set. We also retain \lambda\ll\mu.
The absolutely continuous projection here belongs to edge mass \lambda|_E, not yet to the vertex mass \mu|_E whose strip mass we must bound. We will discard labels over a null set carrying the singular part of the vertex projection and restrict its density to a bounded range. The first deletion loses no selected edge mass, by absolute continuity of its projection, and some finite density bound still retains positive \lambda_{K_0}-mass. The metric construction will then transfer this vertex-density bound from rank coordinates to Euclidean disks and strips.
Proposition 6.1. There is a Borel set G\subset E with \lambda_{K_0}(G)>0, a further subsequence, and a translation and uniform rescaling of each normalized Euclidean plane with the following properties. Over every p\in\pi(G) the limiting graph of the maps L_n has a unique position l(p) in the closed unit disk. With \eta=1/16, there is c_G>0 such that
Attach Euclidean position as an additional compactified coordinate to the vertex measures, and take a weak limit \widetilde\mu. Its restriction by the old-label condition z\in G has position marginal \nu_G satisfying
Consequently every strip of width r has \nu_G-mass at most C'_G r^{d_*-1}, uniformly in its position and direction. Every line has zero \nu_G-mass.
Proof. We first select a positive set with common scale parameters and bounded vertex density in the rank coordinates. After normalizing each configuration at one common rank point, upper radial bounds will make the limiting graph single-valued on that set, and lower radial bounds will give (6.2). Combining this estimate with the vertex density will prove the disk and strip bounds.
For each integer T\ge2 and integer m\ge0, set h_j=T^{-m-j} and consider the points for which \overline B(p,h_0)\subset D and, for every j\ge0, eventually in n,
These are Borel conditions. Indeed, at a fixed admissible radius, U_n and V_n are continuous functions of the center, and eventual validity is a countable union over starting indices followed by a countable intersection over later indices. Taking the further countable intersection over j preserves measurability.
For each point satisfying (6.1), choose T with C_p\le T^\eta, and then choose m large enough. This point satisfies (6.4) at all the selected radii. The countable union over T,m therefore covers the selected good part. Fix one pair T,m retaining positive \lambda_{K_0}-mass. This selection makes no claim of a common starting index.
The bounded density must concern vertices, since their activity will be estimated later. Decompose the pair-coordinate projection of the entire vertex measure as
Choose an area-zero Borel carrier S for \sigma_s, enlarged by any area-zero set on which f is not finite. Delete \pi^{-1}(S) from the selected labels. This loses no good mass because their endpoint projection is absolutely continuous. Next restrict to f(\pi(z))\le M for a sufficiently large finite M, retaining positive \lambda_{K_0}-mass. Denote the resulting set by G; it satisfies
Here we have removed the singular part of the vertex projection and truncated its density; absolute continuity of the endpoint projection alone would not imply (6.5).
Cover D by countably many balls of radius h_0/8 and restrict G to one of positive \lambda_{K_0}-mass. Choose p_0 in its projected good set. Then
Translate and uniformly rescale the maps so that
The scale factor is positive, and (6.4) is unchanged.
We next obtain bounds at every fixed scale, with constants independent of the center. For a homeomorphism, the image of a closed disk is a topological closed disk whose boundary is the image of the boundary circle. Thus
For the first inclusion, a segment from L_n(p) to a missing point closer than V_n(p,h) would first leave the image through a closer boundary point. For the second, a positive maximum of the distance from L_n(p) cannot occur in the interior of the image disk. Also, a point outside B(p,h) has image distance at least V_n(p,h) from L_n(p).
Since T\ge2, the localization gives
Eventually V_n(p_0,h_1)\ge\alpha, so the first image contains B(0,\alpha). Its maximum distance from the possibly nonzero center L_n(p) is at least \alpha. The second image is contained in the unit disk. Therefore
Only the first inequality needs the anchor’s eventual index. The factor 2 occurs because U_n(p,h_1) is measured from L_n(p), rather than from the origin.
Fix p\in\pi(G) and an integer j\ge1. Iterating the finitely many inequalities (6.4), and using V_n\le U_n, gives, eventually in n,
The constants are uniform over G. The index threshold may depend on p,j. We will always fix these parameters before taking the limit.
The upper bounds in (6.7) tend to zero with the scale, while the lower bounds keep distinct rank points separated. We now pass to one graph limit in which both facts can be used, keeping each center and scale fixed before taking the configuration limit.
To put all spatial limits on one subsequence, let X be a compact metric compactification of \mathbb R^2, and take the closures of the graphs of L_n in [0,1]^2\times X. Pass to a subsequence on which these compact sets converge in Hausdorff distance to a closed relation \Gamma. At an interior rank point, each finite-index closed graph contains only the actual graph point, by continuity of L_n.
Fix p\in\pi(G). Its limiting fiber is nonempty by compactness, because |L_n(p)|\le1. Every (p,x)\in\Gamma has graph-point approximations (u_n,L_n(u_n)) at every sufficiently late index of the same subsequence. Since u_n\to p, eventually u_n\in B(p_0,h_0); consequently |L_n(u_n)|\le1. Thus all points in this fiber have finite Euclidean positions.
Suppose x and y are two such positions. Hausdorff convergence provides approximations for both at the same indices. Fix j\ge1. Both rank arguments eventually lie in B(p,h_j), where (6.6) and (6.7) bound the distance between their positions by 4\beta^{j-1}. Passing to the limit and then letting j\to\infty proves x=y, since \beta<1. Call this point l(p). Uniqueness also shows that L_n(p)\to l(p) along the full selected subsequence.
For distinct p,q\in\pi(G) put d=|p-q|<h_0/2. Choose the first j\ge1 with h_j<d; then h_j\ge d/T. The point q lies outside the radius-h_j disk centered at p, so eventually
Both fixed-point sequences converge on our subsequence. Therefore
which proves (6.2). This argument uses a finite number of scales for each fixed pair, not a common threshold over G.
Finally attach compactified position to the vertex and other spatial measures before taking weak limits on this same subsequence. Their old-coordinate projections are unchanged. Their pair-position projections are supported on \Gamma: any compact set disjoint from \Gamma is disjoint from every sufficiently late closed graph, so continuous tests supported there have limiting integral zero. Consequently the enhanced vertex measure restricted by z\in G lies over the unique positions l(\pi(z)). This restriction is made after taking the limit; no convergence of finite-index restrictions to an arbitrary Borel set G is asserted.
If a disk of radius r contains positions over p and q, then (6.2) gives
Thus its pair-coordinate preimage has planar outer area at most a constant times r^{2/(1+\eta)}. Applying (6.5) to that preimage proves (6.3). Using outer area avoids any requirement that a projection of a Borel set itself be Borel.
The support of \nu_G lies in the unit disk. Its intersection with a strip of width r is covered by O(1/r) disks of radius O(r). Summing (6.3) proves the strip estimate; shrinking strips to a line proves that lines have zero mass.
The same enhancement preserves \widetilde\mu_J\le\widetilde\mu and all old marginals, in particular the positive mass \widetilde\lambda_{K_0}\{z\in G\}=\lambda_{K_0}(G). By the enhanced-coordinate form of the earlier crossing inequality, that inequality is also available on this selected set. We will use the strip estimate for its active-vertex measures. The numerical fact needed below is
This is an auxiliary spatial exponent; it is not the exponent saving in the final halving-line bound.
7 Boundary activity and the packing contradiction
We now use the spatial measure constructed above to rule out the assumed sequence of extremal batches. The essential finite observation is that, when the directions of the cutting lines vary little, every participating vertex either lies in one of three narrow strips or is accounted for by a marked token crossing the boundary of a fixed region. We first prove this observation without taking limits.
Lemma 7.1 (Three strips). Let P be a finite subset of \mathbb R^2, let B be a bounded open set, and let D\geq1 satisfy |x|\leq D for x\in B. Suppose that M_0,\ldots,M_m\subset P have the same cardinality and are given by strictly separating cuts
For each i\geq1, choose a bijection from M_{i-1}\setminus M_i to M_i\setminus M_{i-1}. Let C_B count the resulting transfers having exactly one endpoint in B, and let
be the set of distinct participating vertices. Set
and, for q\in\{c_0,c_-,c_+\}, define the closed strip
Then
and consequently
Repeated thresholds may be counted repeatedly in the sum.
Proof. Write t(x)=\nu_0\cdot x and e_i(x)=(\nu_i-\nu_0)\cdot x. For x\in B we have |e_i(x)|\leq\rho, and e_0(x)=0. Put S=S_{c_0}\cup S_{c_-}\cup S_{c_+}. Figure 2 shows the two ranges in which participants in B outside S can occur. We compare their membership with the states attaining the minimum and maximum thresholds.
Figure 2: Projection onto t=\nu_0\cdot x. The shaded bands have half-width 3\rho; their separation is schematic, and in general they may overlap. An initially marked participant in B outside the bands is lost by a state i_- attaining c_-; this endpoint comparison has no gains inside B. The symmetric statement holds for initially unmarked participants and a state i_+ attaining c_+. Token conservation bounds these two numbers by exits and entries, respectively. This is an aggregate count; it does not assign each participant’s own token to a boundary crossing.
Consider first an x\in(A\cap B)\setminus S that is initially marked. Avoidance of S_{c_0} gives t(x)<c_0-3\rho. Since x participates, it is unmarked at some boundary state, and hence t(x)+e_i(x)>c_i\geq c_- at some i. Therefore t(x)>c_- -\rho. Avoidance of S_{c_-} improves this to t(x)>c_-+3\rho. At an index i_- attaining the minimum threshold,
thus x is lost between states 0 and i_-. The existence of even one such x also forces c_0-c_->6\rho. Consequently every initially unmarked y\in P\cap B is still unmarked at state i_-, because
There are therefore no gains anywhere inside B in this comparison, including among vertices lying in the strips.
To count the losses, place one distinct token on each point of M_0. At every step retain the tokens on unchanged marked vertices and move the others along the chosen matching. There is exactly one token on every marked vertex at each state. It follows that
over that prefix of steps. Since all differences between these two states inside B are losses, their number equals this difference and is at most C_B. This bounds the initially marked participants outside the strips; if there are none, the bound holds without imposing a threshold gap.
Now let x\in(A\cap B)\setminus S be initially unmarked. It satisfies t(x)>c_0+3\rho and is marked at some later state, so t(x)<c_++\rho. Avoidance of S_{c_+} implies t(x)<c_+-3\rho. At an index i_+ attaining c_+,
so x is gained by that state. If this class is nonempty, then c_+-c_0>6\rho. Every initially marked y\in P\cap B consequently remains marked at state i_+, since
All differences between these two states inside B are gains, and token conservation bounds their number by C_B. The two classes together contain at most 2C_B vertices, proving (7.1).
The argument includes \theta=0, when the strips are lines. It also includes vertices that change membership several times and return to their initial status: participation requires only that some boundary state differs from the initial one.
We apply this lemma only to states separating consecutive batches. Thus its set A is exactly the set of endpoints participating in the batch exchange graph. A membership change within a batch followed by a return before its end does not by itself contribute a vertex to A or to the measure \mu_J; that vertex may still participate at another batch boundary.
For the rest of this section, suppress the tildes on the enhanced measures from Section 6, and write \widetilde Z for their compact label space, which includes compactified Euclidean position. The condition z\in G always refers to the old rank label, pulled back to \widetilde Z. Thus expressions such as \mu_J(G) refer to the enhanced measures restricted by that condition.
Recall the particular inputs furnished by the preceding construction. There is a dyadic window K_0, a measurable label set G, and limiting measures with
for every Borel set F\subset\widetilde Z and every dyadic J\subset K_0. Here s_J is the limiting fraction of distinct participating batch endpoints. At every dyadic resolution \delta,
The spatial projection \beta of \mu|_G is boundedly supported and satisfies
These masses are unchanged because the enhancement preserved all the original measure projections.
The directions throughout K_0 lie between the directions at its two fixed bracketing times. The common linear normalization sends those two projective directions to distinct fixed directions. Passing to a subsequence selects one of the two projective arcs between them and one of its two oriented lifts. Hence all forward transfer vectors lie in a fixed closed cone \mathcal C of aperture less than \pi. We may enlarge this cone slightly and discard finitely many indices. Each intermediate forward transfer vector is a positive linear combination of the two bracketing forward vectors; this identifies the relevant cone after normalization, including its orientation.
Choose linearly independent covectors \ell_1,\ell_2 in the interior of its dual cone. Thus \ell_j(v)>0 for every nonzero v\in\mathcal C. Choose a bounded open parallelogram
whose interior contains the support of \beta, and fix D\geq\max(1,\sup_{x\in B}|x|).
For every batch choose one perfect matching between its a lost and a gained marked vertices, making this choice once throughout K_0. Follow the resulting system of at most N marked tokens. Each side functional is monotone along every token trajectory, so each token crosses each of the four side levels of B at most once. Therefore there are at most 4N matching transfers with one endpoint inside B and one outside during the entire window K_0.
Let C_n(J) be the number of these transfers during J in configuration n. Let \theta_n(J) be the angular width of the span of its boundary-state directions in the normalized plane. These directions rotate monotonically, and the spans of disjoint windows have disjoint interiors. Thus, for every dyadic partition of K_0,
A diagonal subsequence on the countable family of windows gives limits b_J and \theta_J with
These are limits at a fixed time resolution; no assertion of uniform convergence over resolutions is needed.
Lemma 7.2 (Limiting boundary activity). For each dyadic J\subset K_0,
Proof. Apply Lemma 7.1 to the finite boundary states of J. Continuously orient their unit normals so that the marked sets are given by \nu_i\cdot x<c_i. Their angular span is \theta_n(J), and consequently |\nu_i-\nu_0|\leq\theta_n(J).
Pass further to a subsequence so that the initial normal and the initial, minimum and maximum thresholds converge, allowing infinite threshold limits. This can be done simultaneously for the countably many windows. A finite threshold limit gives a limiting closed strip of half-width 3D\theta_J. A threshold tending to either infinity gives strips that eventually miss every bounded set. Let \mathcal S_J be the union of the nonescaping limiting strips.
Let \alpha_n be the spatial projection of the participating-vertex measure in J, normalized by N_n, and let \alpha be its weak limit. Any continuous function f with 0\leq f\leq1 and compact support in B\setminus\mathcal S_J eventually avoids all three moving strips. Lemma 7.1 therefore gives
Passing to the limit and exhausting the open set by such tests yields \alpha(B\setminus\mathcal S_J)\leq2b_J. Since the positions carrying \mu|_G lie inside B, and \mu_J\leq\mu, it follows that
This argument restricts to G only after weak convergence; no convergence of finite restrictions to G has been assumed.
To bound the remaining term, cover the intersection of a strip of half-width r with the bounded support of \beta by O_G(r^{-1}) disks of radius O(r). Equation (7.4) gives
For larger widths the same estimate follows from the total mass bound after increasing C_G. A line has zero \beta-mass by continuity from above, since d>1. Applying this bound to the at most three limiting strips proves the result, including \theta_J=0.
It remains to combine this activity bound with the endpoint estimate. Fix M\geq1 and subdivide K_0 into dyadic windows of length \delta. By (7.3), the number with s_J>M\delta^{3/4} is at most C M^{-4/3}\delta^{-1}. Each has total \lambda_J-mass \delta, so these windows contribute at most C M^{-4/3} to \lambda_{K_0}(G).
For the other windows, (7.2) gives
There are at most \delta^{-1} windows. Set \alpha=d-1=15/17\in(0,1). Hölder’s inequality, Lemma 7.2, and (7.5) imply
Concavity and the angular budget give
Consequently
where
First let \delta\downarrow0 with M fixed, and then let M\to\infty. This contradicts \lambda_{K_0}(G)>0 and excludes the proposed sequence of extremal batches. Together with the finite reductions, it establishes the uniform little-o activity-packing estimate. The numerical exponent 3/68 concerns only this limiting contradiction; the power saving in the final finite theorem is chosen separately.
8 From activity packing to a power saving
We now turn the uniform activity-packing estimate into a fixed power improvement. The scale is chosen once and then used at every size in an induction. Throughout this section, a sweep is the ordering by increasing values of y-sx as s runs from -\infty to +\infty. Its rank-k marked set consists of the k smallest values. The activity of an interval of sweep steps is the number of distinct points whose membership in that set changes during the interval.
Proposition 8.1. Suppose that, for every \eta>0, there is R_\eta<\infty such that for every generic planar configuration of N points, every rank, and every integer 1\le b\le N with N/b\ge R_\eta, the number of step-disjoint intervals of activity at least b is at most \eta(N/b)^{4/3}. Then there are absolute constants \varepsilon>0 and C such that every such rank sweep has at most CN^{4/3-\varepsilon} switches.
Proof. Write a=4/3, set \eta=(4\cdot2^a)^{-1}, and choose an integer q\ge\max\{4,R_\eta\}. This integer remains fixed. For N\ge4q, put
Then N/(2q)\le b<N/q, so the packing hypothesis applies and N/b\le2q.
Partition the sweep greedily, ending a block when its activity first reaches b, and include any final remainder. Immediately before the last step of a completed block, the activity is at most b-1. A step changes at most two memberships, so the block has at most b+1=d active points. The remainder has fewer than b active points. The completed blocks are step-disjoint, and hence their number is at most
Including the one possible remainder gives at most q^a/2 blocks, since q^a\ge4. Every block uses at most N/q active points.
Let A be the active points of one block and let B be the points outside A that are marked at its initial state. Membership of every point outside A is constant during the block. Therefore restriction to A is a sweep at the fixed rank r=k-|B|: at every state, the marked points of A are exactly its r lowest points. This identity also proves that the switches in the block are exactly the switches of the restricted rank-r sweep over that slope interval. Their number is bounded by the complete-sweep complexity on |A| points.
Let F(n) be the largest switch count among all generic configurations of exactly n points and all ranks, with F(0)=F(1)=0. It is finite, since F(n)\le\binom n2. Set
Choose C so that F(n)\le Cn^\beta for 1\le n<4q. Suppose this bound holds at every size smaller than N\ge4q. If t_j\le N/q are the active-subset sizes of the blocks, the restriction argument and the induction hypothesis give
Here every nonempty subset has size less than N, while empty subsets contribute zero. Thus induction proves the assertion for all sizes and ranks. The selection of q from R_\eta is nonquantitative; this argument does not provide a numerical value of \varepsilon.
Proposition 8.1 and Theorem 2.1 prove Theorem 1.2. It remains to transfer its middle-rank case to the configurations of Theorem 1.1.
For a generic configuration of N=2m points, a pair is halving precisely when its critical slope ties positions m and m+1: there are then m-1 points on each side of its line. The two tied points exchange order, so halving pairs are exactly the middle-rank switches. Each unordered pair has one critical slope in this sweep. The perturbation argument in Section 2 preserves all halving pairs of an arbitrary configuration with no three collinear. Consequently Proposition 8.1, applied to Theorem 2.1, gives the asserted bound for every even size and every such configuration.
8.1 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.
Proof of Corollary 1.3. Take \varepsilon from Theorem 1.2 and set \varepsilon_0=\min\{\varepsilon,1/6\} and \beta=4/3-\varepsilon_0>1. The theorem remains valid with exponent \beta in place of 4/3-\varepsilon.
Dualize a point (a,b) to the line y=b-as. For a generic dual point set P, let V_j be the arrangement vertices with exactly j lines strictly below them. Then |V_j|=S_{j+1}(P): at such a vertex the lines in positions j+1 and j+2 exchange order. The vertices of \Lambda_j are V_{j-1}\cup V_j, with out-of-range sets empty [1, Section 1, p. 2]. Thus Theorem 1.2 bounds every level of M dual lines by O(M^\beta) vertices, uniformly in its rank; its number of edge pieces is one more than its number of vertices. For any line arrangement in the corollary, the dual point set has no three collinear and distinct first coordinates. The perturbation in Section 2 can also preserve the order of those coordinates, so its preservation of all triple-orientation signs preserves every dual vertex’s number of lines below it. The uniform O(M^\beta) level bound therefore holds for every such general-position line arrangement.
Apply Matoušek’s shallow-cutting lemma in the form stated by Agarwal, Aronov, Chan, and Sharir [1, Lemma 3.2 and the following reduction, pp. 10–11]. In dimension two, take r=n/(k+1)\ge1 and q=kr/n+1<2. The cutting has O(rq)=O(n/(k+1)) cells, each crossed by at most n/r=k+1 lines. Within the interior of a cell, the noncrossing lines give a fixed rank offset, so the part of the global level has one fixed local rank in the arrangement of crossing lines. This local rank need not equal k, which is why the all-ranks bound is used. Boundary pieces cost O(k+1) per cell: each crossing line meets the simplex boundary at most twice. An input line not crossing the interior can contribute only along a side or at a vertex. General position allows at most one such line per side and at most two through each vertex; the already counted intersections split their contributions into O(k+1) pieces in total. Since \beta>1, these terms are absorbed by the local O((k+1)^\beta) bound. The cited shallow-cutting reduction now gives
For a generic point set Q, every k-set consists of the k smallest values of some linear functional. Normal directions with positive second coordinate give the bottom-k sweep, while those with negative second coordinate give complements of the bottom-(n-k) sweep. The horizontal directions are included by limits, since first coordinates are distinct. Hence the number of k-sets is at most S_k(Q)+S_{n-k}(Q)+2. In the dual arrangement, S_k(Q)=|V_{k-1}|; vertical reflection sends the vertices counted by S_{n-k}(Q)=|V_{n-k-1}| to V_{k-1} of the reflected arrangement. Each of these two vertex sets lies on a k-th level, so the level bound just proved applies twice. Finally, for any fixed point set, choose one strict separating line for each of its finitely many k-sets. All these strict separations survive a sufficiently small generic perturbation. Its original number of k-sets is therefore no larger than the generic count.
References
- [1]Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, and Micha Sharir. On Levels in Arrangements of Lines, Segments, Planes, and Triangles. Discrete & Computational Geometry, 19:315–331, 1998. Numbered and page locators refer to the author manuscript dated August 30, 1997. doi:10.1007/PL00009348.
- [2]M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi. Crossing-Free Subgraphs. Annals of Discrete Mathematics, 12:9–12, 1982. doi:10.1016/S0304-0208(08)73484-4.
- [3]Estrella Alonso, Mariló López, and Javier Rodrigo. An Improvement of the Upper Bound for the Number of Halving Lines of Planar Sets. Symmetry, 16(7):936, 2024. doi:10.3390/sym16070936.
- [4]Shiri Artstein-Avidan and Boaz A. Slomka. The Fundamental Theorems of Affine and Projective Geometry Revisited. Communications in Contemporary Mathematics, 19(5):1650059, 2017. doi:10.1142/S0219199716500590, arXiv:1604.01762.
- [5]Jonathan M. Borwein, James V. Burke, and Adrian S. Lewis. Differentiability of Cone-Monotone Functions on Separable Banach Space. Proceedings of the American Mathematical Society, 132(4):1067–1076, 2004. doi:10.1090/S0002-9939-03-07149-1.
- [6]Yves Chabrillac and Jean-Pierre Crouzeix. Continuity and Differentiability Properties of Monotone Real Functions of Several Real Variables. Mathematical Programming Study, 30:1–16, 1987. doi:10.1007/BFb0121151.
- [7]Tamal K. Dey. Improved Bounds for Planar k-Sets and Related Problems. Discrete & Computational Geometry, 19(3):373–382, 1998. doi:10.1007/PL00009354.
- [8]Paul Erdős, László Lovász, A. Simmons, and Ernst G. Straus. Dissection Graphs of Planar Point Sets. In A Survey of Combinatorial Theory, pages 139–149, North-Holland, 1973. https://users.renyi.hu/~p_erdos/1973-07.pdf.
- [9]Frank Thomson Leighton. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks. Foundations of Computing, MIT Press, 1983. https://mitpress.mit.edu/9780262121040/complexity-issues-in-vlsi/.
- [10]László Lovász. On the Number of Halving Lines. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica, 14:107–108, 1971.
- [11]Gabriel Nivasch. An Improved, Simple Construction of Many Halving Edges. In Surveys on Discrete and Computational Geometry: Twenty Years Later, pages 299–305, American Mathematical Society, 2008. doi:10.1090/conm/453/08804.
- [12]János Pach, József Solymosi, and Gábor Tardos. Crossing Numbers of Imbalanced Graphs. Journal of Graph Theory, 64(1):12–21, 2010. doi:10.1002/jgt.20435.
- [13]János Pach, William Steiger, and Endre Szemerédi. An Upper Bound on the Number of Planar k-Sets. Discrete & Computational Geometry, 7(2):109–123, 1992. doi:10.1007/BF02187829.
- [14]Anna Pascoletti and Fabio Zanolin. A Path Crossing Lemma and Applications to Nonlinear Second Order Equations under Slowly Varying Perturbations. Le Matematiche, 65(2):121–168, 2010. doi:10.4418/2010.65.2.13.
- [15]Kevin R. Payne and Davide Francesco Redaelli. A Primer on Semiconvex Functions in General Potential Theories. 2025. Version 3, 15 April 2025; Appendix B, Corollary B.4, p. 117. arXiv:2303.14477, https://arxiv.org/abs/2303.14477v3.
- [16]Rom Pinchasi. Halving Lines and Measure Concentration in the Plane. In Proceedings of the 25th Annual Symposium on Computational Geometry, pages 141–147, Association for Computing Machinery, 2009. doi:10.1145/1542362.1542393.
- [17]Hans Rademacher. Über partielle und totale Differenzierbarkeit von Funktionen mehrerer Variabeln und über die Transformation der Doppelintegrale. Mathematische Annalen, 79(4):340–359, 1919. doi:10.1007/BF01498415.
- [18]L. Siebenmann. The Osgood–Schoenflies Theorem Revisited. Russian Mathematical Surveys, 60(4):645–672, 2005. doi:10.1070/RM2005v060n04ABEH003672.
- [19]Leon Simon. Introduction to Geometric Measure Theory. Tsinghua lecture notes, 2014. 2014 draft. https://web.stanford.edu/class/math285/ts-gmt.pdf.
- [20]Géza Tóth. Point Sets with Many k-Sets. Discrete & Computational Geometry, 26(2):187–194, 2001. doi:10.1007/s004540010022.
- [21]Marcelo Viana. Disintegration into Conditional Measures: Rokhlin’s Theorem. n.d. Undated author lecture notes. https://w3.impa.br/~viana/out/rokhlin.pdf.