Но это было ответвление. А вот почему я исходно эту задачу вспомнил.

Представим себе, что на плоскости заданы два бесконечных множества точек, таких, что в любой ограниченной области точек лишь конечное число. Тогда можно задать такой вопрос — можно ли точки из одного множества сопоставить с точками из другого так, чтобы эту биекцию в смысле какой-нибудь « функции цены » нельзя было бы улучшить конечной перестройкой (то есть изменением сопоставлений для конечного их числа).

Точнее — очень естественно в качестве функции цены взять "сумму" \sum_i F(a_i,b_i),
где точке a_i сопоставлена b_i, а F(a,b) — какая-нибудь заданная наперёд функция цены одной перевозки. Например, логично взять в качестве F(a,b) расстояние d(a,b) (вот и параллель с задачей о непересекающихся отрезках) или какую-нибудь его степень
d(a,b)^{\gamma}, где \gamma>0.

Тут слово "сумма" взято в кавычки, потому что ряд, конечно, расходится. Но если мы меняем лишь конечное число пар — то разница между тем, что было и тем, что стало, вполне себе корректно определена (мы просто сокращаем совпадающие слагаемые).

Сами же множества точек можно (и это вполне естественно) брать случайными, задаваемыми пуассоновским процессом. То есть — допустим, что наличие точек в непересекающихся множествах это независимые события (а красные и синие точки выбираются независимо друг от друга). И вероятность того, что синяя (или красная) точка есть в маленьком квадратике площади S, (примерно) равна \lambda*S.

В некотором приближении — можно сказать, что мы нарежем плоскость на такие квадратики, и для каждого « подбросим монетку », чтобы решить, есть ли там точка. (И так два раза — цвета два). Или — что мы нальём на светочувствительную плоскость ровным слоем не слишком сильно радиоактивный раствор, и зафиксируем, где за данное время произошли распады (атомы как раз распадаются независимо).

Да — изменение биекции в конечном числе точек разбивается на циклы:
было
точка a_1 сопоставлена b_1,
точка a_2 сопоставлена b_2,
…
точка a_k сопоставлена b_k;
стало
точка a_1 сопоставлена b_2,
точка a_2 сопоставлена b_3,
…
точка a_k сопоставлена b_1.

Поэтому вместо того, чтобы говорить, что биекция оптимальна относительно всех конечных перестроек — достаточно попросить, чтобы её нельзя было улучшить никакой циклической перестановкой сопоставлений.

Только — а вот есть ли такие сопоставления?