The Setting
The packing problem concerns intervals of a planar sweep whose endpoint selections differ in many point indices. Let be an indexed configuration of points, where , and write . The sweep projection at a real slope is the function in (1). (1)✦
A subset is projection-separated at slope when its points precede all points outside in the strict projection order, as in (2). (2)✦
The directed set distance between subsets of counts the indices in but not in , as specified in (3). (3)✦
A rank sweep sequence with steps consists of slopes and marked sets , indexed by , such that is projection-separated at and the conditions in (4) hold. (4)✦
The state distance in is the directed distance between the marked sets at states and , as in (5). (5)✦
Checkpoints and Intervals
For a state of and a positive integer , the eligible checkpoint set is the set of states of later than and at distance at least from .✦ When is nonempty, the next checkpoint of after at threshold is the least member of , as in (6). (6)
For a state of and a positive integer , a greedy checkpoint sequence of distance in starting at is a sequence of states satisfying (7); each interval between consecutive checkpoints is a complete batch, and is the number of these batches. (7) Write for the library’s chosen greedy checkpoint sequence, and for its number of complete batches.
The step set of an interval with endpoints is . A finite family of pairs of states of is step-disjoint when distinct pairs have disjoint step sets, as in (8). (8)✦
The Claim
Theorem 1. Let be a rank sweep sequence. For a state and a positive integer with , the next checkpoint satisfies (9)✦ Let be an integer, and let be a finite step-disjoint family of pairs with and . Then (10)✦
In the paper, the result reads: fix a rank and an integer , put , start at the first state and end each batch at the first subsequent state at distance from its start, repeating while possible; if complete batches result, every collection of intervals with disjoint step sets and endpoint distance at least has at most members.
What Is Checked
The checkpoint identity (9) and packing bound (10) are stated over finite rank sweep sequences, with positive distance thresholds and, for the packing bound, ordered step-disjoint intervals. For every starting state and positive integer , the chosen greedy checkpoint sequence has consecutive checkpoint distance , and every interval with and contains one of its later checkpoints in .✦