The Setting
As a separating line changes slope, points leave and enter a marked set of fixed size. The exchange graph joins every departing point to every entering point in the same batch.✦ The question is how partitions of the exchange edges into classes constrained by supporting lines control the number of crossings.
Let , and let be a configuration, with . The sweep projection at slope is the linear functional in (1). (1)✦ A slope separates a marked set when every marked point has smaller projection than every unmarked point.✦
A uniform exchange system with parameters consists of sample slopes and marked sets satisfying (2), including separation at every sample and exchange distance between consecutive samples. (2)✦ The leaving set and entering set of batch are the differences in (3). (3)
Let be the exchange edge set, let be its endpoint set, and let denote the number of these endpoints. (4) A straight-line drawing of a configuration is a geometric graph with finite vertex and ordered edge sets, with both endpoints of every edge among its vertices and for every edge . The exchange drawing has vertex set , edge set , and edge segments .✦
Two edges cross when their open segments intersect.✦ Write for the set of distinct unordered crossing edge pairs.✦ A straight-line drawing has no triple edge intersections when a point in the open segments of two distinct edges belongs to no third edge segment, including its endpoints.✦
A configuration is in general position when its points are distinct and no three are collinear.✦ Collinearity is measured by the orientation determinant (5). (5)✦ A configuration , with , has distinct abscissae when is injective; this is a separate condition from general position.
Owners and Supporting Lines
Assume and put , with addition modulo . Fix bijective enumerations and . The cyclic perfect matching with shift is (6). (6) For finite sets and a bijection , the matching-induced transport is the bijection which fixes and sends each leaving element to .
The batch token transport is the transport induced by .✦ The cumulative token transport is the composition specified in (7). (7)✦ An edge token trace of is a triple , where , and , satisfying (8). (8)✦ For a choice of one trace for each , the convex owner is the map on given by .
The complementary reflected system of is the exchange system obtained by replacing by and by , keeping the sample slopes and exchange distance and replacing the mark count by .✦ The concave owner of is the owner map defined from the convex owner of by (9). (9)
For points with , their slope and supporting line height are the functions in (10); write for an edge . (10) A convex cover of a drawing with label set is an owner map such that every segment lies on or above every supporting line in its owner class✦; a concave cover has the reversed inequality.✦ Denote these sets of covers by and , respectively, with the conditions in (11) applying whenever , and . (11)
The Claim
Theorem 1. Let be a uniform exchange system with , and let be its exchange drawing. The convex and concave owners define covers: (12)✦ (13)✦ For every exchange edge , the owners satisfy (14)✦ (15)✦ If is in general position, its abscissae are distinct, and has no triple edge intersections, then (16)✦
In the paper, the result reads: for a consecutive window of batches of distance with distinct exchange endpoints, the exchange edges partition into at most convex polygonal chains and into at most concave polygonal chains, and have at most properly crossing pairs.
What Is Checked
The cover statements (12) and (13), with the owner restrictions (14) and (15), are stated over uniform exchange systems with ; the crossing bound (16) additionally assumes general position, distinct abscissae and no triple edge intersections. Every exchange edge admits an edge token trace.✦