The Setting
A sweep of lines through a planar configuration gives a changing set of points below the sweeping line. The question concerns collections of intervals during which many points change membership.
A planar configuration is an indexed map , where a planar point is a pair of real numbers.✦ For planar points , the orientation determinant and the slope are defined by (1): (1) A planar configuration is in general position if is injective and for distinct indices .✦ A planar configuration is generic if it is in general position, its first coordinates are pairwise distinct, its unordered point pairs have pairwise distinct slopes, and, for any three distinct unordered pairs, the intersection of the open segments of the first two pairs is disjoint from the closed segment of the third pair.✦ Unordered pairs are represented by indices .
The sweep projection at slope is the function in (2): (2)✦ A marked set is separated at slope if whenever and .✦ The directed set distance of marked sets and is .✦
The critical slope set of a planar configuration is the finite set in (3): (3)✦ A traversal of a finite slope set is a sequence of cuts whose interior terms are exactly .✦ The canonical critical slope traversal of a planar configuration is the chosen traversal of .✦ The intercritical sample slopes of the canonical critical slope traversal are the midpoints in (4): (4)✦
A rank- sweep sequence of a planar configuration is a sequence of strictly increasing slopes and -element marked sets, separated at their respective slopes, such that consecutive marked sets have directed set distance at most one.✦ For generic and , the canonical rank- sweep has marked sets separated at the intercritical sample slopes , where is the size of the canonical critical slope traversal.✦
The active set of a finite family relative to a member is the set of indices whose membership differs from its membership in in at least one member of the family.✦ The interval active set of a sweep on , with , is the active set of relative to ; both sets are given in (5): (5) The activity of is . A collection of sweep intervals is step-disjoint if the sets of steps are pairwise disjoint for distinct .✦
Exchange Batches
A system of distance- exchange batches on is a sequence of strictly increasing slopes and -element marked sets , separated at the respective slopes, with the distances in (6): (6)✦ A generic batch configuration is a system of distance- exchange batches of rank on a generic -point configuration, where are positive integers and is nonnegative.✦ A sweep embedding of a generic batch configuration is a strictly increasing choice of indices in the canonical rank- sweep of its underlying configuration, with , satisfying (7): (7)✦
The Claim
Theorem 1. For every there is such that every generic batch configuration with a sweep embedding and satisfies (8): (8)✦ For every there is such that, whenever is generic, , is a positive integer and , every finite step-disjoint collection of intervals of the canonical rank- sweep with for every satisfies (9): (9)✦
In the paper, the result reads: for every there is a finite such that, for every generic -point configuration, every rank and every integer with , any collection of intervals with disjoint step sets and activity at least has at most members.
What Is Checked
The assertions are stated over canonical rank sweeps of generic planar configurations and positive generic batch configurations with sweep embeddings.