OctoInformBeta

OpenAI preprint, September 2026 · §2. Sweeps, activity, and exchange graphs

Lemma 2.2: A distance bound at a feasible shifted rank, and a positive bound at the original rank

Sweep activity forces endpoint separation.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A projection sweep follows the set of lowest points as the slope varies. The question is how membership changes over an interval constrain its endpoint sets at nearby ranks.

For a nonnegative integer nn, let V={0,…,n−1}V=\{0,\ldots,n-1\} and let P:V→ℝ2P:V\to\mathbb R^2 be an indexed planar configuration. A planar point p=(p1,p2)p=(p_1,p_2) is a pair of real numbers.✦ The sweep projection πs\pi_s at a real slope ss is the real-valued function on ℝ2\mathbb R^2 in (1), and the slope ℓ(p,q)\ell(p,q) of planar points p,q∈ℝ2p,q\in\mathbb R^2 is the real number given there. πs(p)=p2−sp1,ℓ(p,q)=q2−p2q1−p1.\pi_s(p)=p_2-sp_1, \qquad \ell(p,q)=\frac{q_2-p_2}{q_1-p_1}.(1)

The orientation determinant orient⁡(p,q,r)\operatorname{orient}(p,q,r) of planar points p,q,r∈ℝ2p,q,r\in\mathbb R^2 is the signed area determinant in (2).✦ A configuration PP is in general position if its point map is injective and this determinant is nonzero for every triple of distinct indices.✦ orient⁡(p,q,r)=det⁡(q−p,r−p)=(q1−p1)(r2−p2)−(q2−p2)(r1−p1).\operatorname{orient}(p,q,r) =\det(q-p,r-p) =(q_1-p_1)(r_2-p_2)-(q_2-p_2)(r_1-p_1).(2)

A generic configuration PP is a configuration in general position whose points have pairwise distinct first coordinates and whose unordered pairs, represented by i<ji<j, have pairwise distinct slopes, with the additional condition that no point in the open segments of two distinct pairs lies on the closed segment of a third distinct pair.✦

For a real slope ss and a rank r∈ℕr\in\mathbb N, the family ℒr(s)\mathcal L_r(s) of projection-separated sets of rank rr consists of the subsets of VV specified in (3). ℒr(s)={M⊆V:|M|=r,πs(Pi)<πs(Pj)for every i∈M,j∈V\M}.\mathcal L_r(s)= \left\{M\subseteq V:\ |M|=r,\quad \pi_s(P_i)<\pi_s(P_j)\ \text{for every }i\in M,\ j\in V\setminus M\right\}.(3)✦

The directed set distance δ(X,Y)\delta(X,Y) of subsets X,Y⊆VX,Y\subseteq V counts the indices in XX outside YY, as in (4). δ(X,Y)=|X\Y|.\delta(X,Y)=|X\setminus Y|.(4)✦

For a finite family M=(Mi)i∈IM=(M_i)_{i\in I} of subsets of VV and a reference index i0∈Ii_0\in I, the active set A(M;i0)A(M;i_0) consists of indices whose membership differs from that in Mi0M_{i_0} at some member of the family; its cardinality is the activity. A(M;i0)=⋃i∈I(Mi△Mi0).A(M;i_0)=\bigcup_{i\in I}(M_i\mathbin{\triangle}M_{i_0}).(5)✦

Sweep Sequences

A rank kk sweep sequence S=(si,Mi)i=0TS=(s_i,M_i)_{i=0}^T on PP, where TT is a nonnegative integer, consists of strictly increasing sample slopes and marked sets Mi∈ℒk(si)M_i\in\mathcal L_k(s_i), with δ(Mi,Mi+1)≤1\delta(M_i,M_{i+1})\le1 at every step 0≤i<T0\le i<T.✦ For a rank sweep sequence S=(si,Mi)i=0TS=(s_i,M_i)_{i=0}^T and state indices u,v∈{0,…,T}u,v\in\{0,\ldots,T\}, the endpoint distance dS(u,v)d_S(u,v) is the directed set distance from MuM_u to MvM_v.✦ When u≤vu\le v, the interval active set AS(u,v)A_S(u,v) consists of indices whose membership differs from that in MuM_u at some state from uu through vv, as in (6). dS(u,v)=δ(Mu,Mv),AS(u,v)=⋃i=uv(Mi△Mu).d_S(u,v)=\delta(M_u,M_v), \qquad A_S(u,v)=\bigcup_{i=u}^v(M_i\mathbin{\triangle}M_u).(6)

The critical-slope set C(P)C(P) of an indexed planar configuration P:V→ℝ2P:V\to\mathbb R^2 is the finite set of slopes of its pairs of distinct indices, represented by i<ji<j, in (7).✦ For a finite set C⊂ℝC\subset\mathbb R with mm members, a critical slope traversal of CC is a strictly increasing list of cuts t0<⋯<tm+1t_0<\cdots<t_{m+1} whose interior cuts are precisely CC.✦ C(P)={ℓ(Pi,Pj):i,j∈V,i<j}.C(P)=\{\ell(P_i,P_j):i,j\in V,\ i<j\}.(7)

The canonical critical slope traversal t0<⋯<tm+1t_0<\cdots<t_{m+1} of a finite set C⊂ℝC\subset\mathbb R with mm members is the list of its members in increasing order, preceded by one cut below all its members and followed by one above them.✦ For any critical slope traversal t0<⋯<tm+1t_0<\cdots<t_{m+1} of a finite set C⊂ℝC\subset\mathbb R, the intercritical sample slope sis_i in the iith gap is the midpoint in (8). si=ti+ti+12,0≤i≤m.s_i=\frac{t_i+t_{i+1}}2, \qquad 0\le i\le m.(8)✦ For a generic PP and 0≤r≤n0\le r\le n, write S(r)S^{(r)} for its canonical rank rr sweep, a rank sweep sequence with m+1m+1 states, where mm is the interior-cut count of the canonical traversal of C(P)C(P).✦

The Claim

Theorem 1. Let c,k∈ℕc,k\in\mathbb N, let II be finite, and let si∈ℝs_i\in\mathbb R and Mi∈ℒk(si)M_i\in\mathcal L_k(s_i) for every i∈Ii\in I. Choose i0,i1∈Ii_0,i_1\in I such that si0≤si≤si1s_{i_0}\le s_i\le s_{i_1} for every i∈Ii\in I. Suppose that the projections of the indexed points are pairwise distinct at each endpoint slope. If 4c≤|A(M;i0)|4c\le|A(M;i_0)|, at least one alternative in (9) holds. k+c≤n,∃E∈ℒk+c(si0),E′∈ℒk+c(si1):δ(E,E′)≥c,orc≤k,∃E∈ℒk−c(si0),E′∈ℒk−c(si1):δ(E,E′)≥c.\begin{gathered} k+c\le n,\qquad \exists E\in\mathcal L_{k+c}(s_{i_0}),\ E'\in\mathcal L_{k+c}(s_{i_1}):\quad \delta(E,E')\ge c, \\ \text{or} \\ c\le k,\qquad \exists E\in\mathcal L_{k-c}(s_{i_0}),\ E'\in\mathcal L_{k-c}(s_{i_1}):\quad \delta(E,E')\ge c. \end{gathered}(9)✦

Let PP be generic, let k≤nk\le n, and take state indices 0≤u≤v≤m0\le u\le v\le m. For c∈ℕc\in\mathbb N with 4c≤|AS(k)(u,v)|4c\le|A_{S^{(k)}}(u,v)|, at least one alternative in (10) holds. k+c≤nanddS(k+c)(u,v)≥c,orc≤k,k−c≤nanddS(k−c)(u,v)≥c.\begin{gathered} k+c\le n\quad\text{and}\quad d_{S^{(k+c)}}(u,v)\ge c, \\ \text{or} \\ c\le k,\quad k-c\le n\quad\text{and}\quad d_{S^{(k-c)}}(u,v)\ge c. \end{gathered}(10)✦

For any rank sweep sequence SS and indices 0≤u≤v≤T0\le u\le v\le T with |AS(u,v)|>0|A_S(u,v)|>0, the endpoint distance satisfies (11). dS(u,v)≥1.d_S(u,v)\ge1.(11)✦

In the paper, the result reads: for a generic nn-point configuration and a rank kk, any collection of intervals of activity at least an integer b≥4b\ge4 splits into two classes, the first having endpoint distance at least ⌊b/4⌋\lfloor b/4\rfloor at rank k+⌊b/4⌋k+\lfloor b/4\rfloor and the second having that distance at rank k−⌊b/4⌋k-\lfloor b/4\rfloor, with every rank used by a nonempty class feasible, while for 1≤b<41\le b<4 each interval of activity at least bb has endpoint distance at least one at rank kk.

What Is Checked

The setting of (9) is a finite family of projection-separated sets on an arbitrary indexed planar configuration, with extremal sample slopes and distinct endpoint projections; (10) concerns canonical sweeps of a generic configuration with k≤nk\le n, whereas (11) concerns arbitrary rank sweep sequences.