By Paolo Baldan (1) and Roberto Bruni (2)
(1) Univ. of Padova, Department of Pure and Applied Mathematics
(2) Univ. of Pisa, Computer Science Department
It’s the end of the extra time of the final the European football championship. It has been a wonderful match between Italy and Germany, ended with the incredible result of 4-4 (or maybe it wasn’t exactly that way). The title is going to be assigned by penalties. The Italian trainer asks their players to position in the left half of the field, and relax by organising in pairs and exchanging passes. However, if pairs are formed in a completely random way, the trajectories of the balls may intersect and there is a concrete risk of ball collisions, making the players nervous (see the red trajectories in the picture below). This must be avoided.
So, the trainer observes the positions of the players in the pitch and starts wondering whether there is an easy way of pairing the players in a way that their passes will not intersect. The trainer observes that if the field of play is seen as a Cartesian plane, with origin at the corner flag, then the players can be assigned cartesian coordinates, and paired according to the lexicographic order on such coordinates: the first with the second, the third with the fourth, and so on. Unfortunately, time is running out and the trainer does not have a way of determining the coordinates of players, but he sees a long rope laying outside the field and has a better idea. Can you guess which solution has come to mind to the trainer? The trainer observed that one could equivalently use polar coordinates instead of Cartesian ones. Let Pi (i ∈{1,…,2n} be the (even number of) players. Let us consider for each player Pi by its polar coordinates (θi,ρi) on the plane, taking as origin the left lower corner (hence θ will range in [0,π∕2]). Assume, for the moment, that the angles for all players are different. In this case, the trainer can simply proceed by ordering the players Pi according to their angle θi, and pair them according to this order, the first with the second, the third with the fourth and so on. Clearly, the segments connecting the various pairs of players do not intersect as they lay on different slices of the plane. The complexity of the procedure is that of sorting, i.e., O(n log n).
The procedure can be simply adapted when the hypothesis that θi≠θj for i≠j does not hold. In fact, it is easy to see that it suffices to sort the players according to the pair (θi,ρi), lexicographically, and proceed as before.
But what is the advantage of using polar coordinates and what has this to do with the rope? The point is that the trainer implements the described procedure without computing explicitly the polar coordinates and their ordering. Rather it just uses the (sufficiently long) rope, tied at the corner flag spike. Then starting with the rope aligned with the touchline of the field, he rotates going towards the goal post. The order of the players is then given by the order in which they meet the rope (when there are no players aligned w.r.t. the corner, but adapting the procedure when this does not hold is again trivial). This is illustrated in the picture below:
Unfortunately the players are superstitious: half of them wear black shoes and half of them wear red shoes and would like to form pairs of players with different shoes colours only. Can you still help the trainer to find a (decently efficient) algorithm for pairing the players in a way that avoids any risk of collisions, namely such that the trajectory segments connecting paired players do not intersect?
Assuming that players in pairs can understand when their trajectories intersect, in order to solve the problem the trainer can use an iterative procedure. Initially the players randomly pair just respecting the constraint on the colour of the shoes. If there are no trajectories which intersect, we are done. If instead the trajectories corresponding to two pairs of players intersect, they switch partners.
This procedure must converge, because there are only a finite number of possible pairings and at each switch the sum of the length of all trajectories will decrease: in fact, the length of one side of a triangle (see dashed lines in the figure below) must be less than the sum of the lengths of the other two sides (red lines).
Well, to be precise, this works assuming that there not four players – two players with red shoes and two players with black shoes – on the same line. But this is unlikely to happen, isn’t it?
Let us call a played red or black depending on his shoes colour. Observe that if 2n is the number of players then any of the n red players can reduce its distance from the partner at most n – 1 times. Since any exchange reduce the distance for two red players, the procedure terminates in at most n(n – 1)∕2 steps.