Линейное упорядочивание точек

[Mihaylo]

Задача не учебная, формулируется по практическим соображениям. Я сам не математик, поэтому прошу отнестись с пониманием. Ожидаю дополнительных вопросов.

Задача:
Две точки ($x_1$, $y_1$) и ($x_2$, $y_2$) в единичном прямоугольнике нужно пронумеровать (№1, №2 или №2, №1) таким образом, чтобы функция $order = f(x_1, y_1, x_2, y_2)$ была с "минимальной нелинейностью". Здесь мы принимаем, что, если $order = 0$, то точки нумеруются как №1 и №2, если же $order = 1$, то имеет место обратная нумерация №2 и №1. Если непонятно сразу, то смотрите примеры ниже.

Примеры наверняка не самых оптимальных решений:

1. $order = (x_1 > x_2) \wedge ({x_1 = x_2} \vee {y_1 > y_2})$

2. $order = (\sqrt{x_1^2+y_1^2} > \sqrt{x_2^2+y_2^2}) \wedge (\sqrt{x_1^2+y_1^2} = \sqrt{x_2^2+y_2^2} \vee ATAN_2(x_1, y_1) > ATAN_2(x_2, y_2))$

Иными словами, предложены сортировка по декартовым координатам или по полярным координатам.

А есть что-то получше?

[wrest]

Mihaylo
Мне кажется, будет полезно глянуть в тему «Комплексные числа - можно ли упорядочить?»

[Mihaylo]

wrest
Я прочитал тему по ссылке, но у меня мозг взрывается.

Может быть разница в том, что в той теме просят в некотором смысле идеальное упорядочивание, при этом у меня пойдет и такой совет:

meduza в сообщении #292774 писал(а):

Принципиально можно (например сравнивать веществ. части, а если они равны -- то мнимые), но толку от такого упорядочивания нет абсолютно никакого.

В моем случае смысл присутствует, но хотелось бы некоего приближения в оптимальности. Наверное более точным критерием оптимальности была бы вероятность того, что две случайные декартовы точки не находятся в точке разрыва функции упорядочивания...

[wrest]

Mihaylo в сообщении #1608838 писал(а):

моем случае смысл присутствует, но хотелось бы некоего приближения в оптимальности.

А что вы под этим ("оптимальностью") подразумеваете? Ну например тройки фамилия-имя-отчество так вот и упорядочивают, обычно.

[Mihaylo]

Давайте возьмем точки (0.22, 0.78) и (0.5, 0.66).
У нас есть два варианта упорядочивания (декартовый и полярный). Если мы проанализируем некоторые окрестности точек, то мы обнаружим линейность в довольно больших интервалах. $order$ в этих интервалах не будет изменяться скачкообразно от нуля к единице, или от единицы к нулю.

Наверное важны моменты, когда интервалы стремятся к бесконечно малым величинам.

[Sender]

Т.е. вы хотите непрерывного взаимно однозначного отображения прямоугольника на прямую? Это, увы, невозможно.

[wrest]

Mihaylo в сообщении #1608843 писал(а):

Наверное важны моменты, когда интервалы стремятся к бесконечно малым величинам.

От этого тоже толку не будет. Ну вот кривые Пеано непрерывные. Но биекции все равно нет. Не говоря уже о какой-то практической пользе - её тоже нет.

[diletto]

Mihaylo
Можно наивный вопрос? Если задача прикладная, то, может быть, достаточно "нарисовать" в квадратике плотную рациональную сетку (с шагом заведомо меньшим, чем достижимая точность измерения координат точек), упорядочить её хоть зигзагом, хоть по спирали, и приписывать входящую точку ближайшему узлу сетки?

[Mihaylo]

Sender в сообщении #1608845 писал(а):

непрерывного взаимно однозначного отображения прямоугольника на прямую?

Не на прямую, а на (false, true).

-- 12.09.2023, 17:47 --

Определение. Булева функция линейна (непрерывна) в окрестностях точек $(x_1, y_1)$ и $(x_2, y_2)$, если в этих окрестностях ее значение не изменяется. Это же верное определение?

Нужно найти такую булевую функцию, которая "наименьшим образом изрезана нелинейностью". Формулировка неточная, нужно как-то додумать.

Как сравнить друг с другом по степени нелинейности те две функции выше, которые упорядочивают точки в декартовых и полярных координатах?

[Mihaylo]

Я тут подумал и понял, что можно уточнить задачу: точки $(x_1, y_1)$ и $(x_2, y_2)$ произвольны, но расстояние между ними не меньше некоторого конечного расстояния $d$. Если точки близко расположены, то смысл такого выбора точек теряется.

[Mihaylo]

Придумал метод триангуляции. Измеряем расстояние между точками $(x_1, y_1)$, $(x_2, y_2)$ и $(0, 0)$, $(1, 0)$.
$d_{11} = \sqrt{x_1^2 + y_1^2}$
$d_{12} = \sqrt{(x_1-1)^2 + y_1^2}$
$d_{21} = \sqrt{x_2^2 + y_2^2}$
$d_{22} = \sqrt{(x_2-1)^2 + y_2^2}$

Функция упорядочивания
$order = ((\left\lvert d_{11} - d_{21}\right\rvert > \left\lvert d_{22} - d_{12}\right\rvert) \wedge (d_{11} < d_{21}) \vee (\left\lvert d_{11} - d_{21}\right\rvert < \left\lvert d_{22} - d_{12}\right\rvert) \wedge (d_{12} > d_{22}))$

[Mihaylo]

Нашел более простую функцию упорядочивания.
Самую первую функцию упорядочивания в декартовых координатах можно переписать следующим образом:
$order = (x_1 - x_2 > 0) \vee ((x_1 - x_2 = 0) \wedge (y_1 - y_2 > 0))$

При рассмотрении ограничения задачи
$(x_1 - x_2)^2 + (y_1 - y_2)^2 \geqslant d^2$, $d > 0$
можно вывести новую функцию упорядочивания:
$order = (x_1 - x_2 > d_0) \vee ((x_1 - x_2 \leqslant d_0) \wedge (y_1 - y_2 > d_0))$,
где $d_0 > 0$.
Нехитрым способом можно доказать, что при $d_0 \leqslant d \cdot \frac{\sqrt{2}}{2}$ новая функция упорядочивания непрерывна для любой пары точек, между которыми расстояние не менее $d > 0$.

Итак, если я нигде не ошибся, то одна из простейших искомых функций для двух точек найдена.

---------------------------------------------------

Теперь задача усложняется. Дано n точек, расстояние между каждой парой точек не менее $d > 0$. Нужно найти непрерывную функцию упорядочивания.

Например, даны точки $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5)$. Функция упорядочивания может выдать результат вроде такого $3, 2, 4, 1, 5$.

Вопрос: Можно ли говорить, что в качестве функция упорядочивания можно использовать любой стандартный алгоритм сортировки, который будет многократно использовать функцию упорядочивания (сравнения) двух точек? Кажется надо доказать транзитивность порядка.

[Mihaylo]

Свойством транзитивности такое сравнение двух точек не обладает (есть простой контрпример). Поэтому применить алгоритмы сортировки невозможно. Наверное все ждали подобное резюме.

Но все же. Даже в таком виде: нетранзитивное упорядочивание (сравнение) точек и стандартные алгоритмы сортировки - все это удовлетворительное для практики приближение к идеалу. Жаль, что теоретическое исследование пока неполное...

[tolstopuz]

Mihaylo в сообщении #1609120 писал(а):

можно вывести новую функцию упорядочивания:
$order = (x_1 - x_2 > d_0) \vee ((x_1 - x_2 \leqslant d_0) \wedge (y_1 - y_2 > d_0))$,
где $d_0 > 0$.

Во-первых, $A \vee (\bar{A} \wedge B)=A \vee B$, поэтому формула упрощается. Во вторых, это отношение не антирефлексивно, что гораздо хуже нетранзитивности.

Возьмите $d_0=1, (x_1,y_1)=(1,-1), (x_2,y_2)=(-1,1)$. Чему равен $order$? Теперь поменяйте их местами: $(x_1,y_1)=(-1,1), (x_2,y_2)=(1,-1)$. Чему теперь равен $order$?

[Mihaylo]

Извиняюсь, следовало написать так:

$order = (x_1 - x_2 > d_0) \vee ((\left\lvert x_1 - x_2 \right\rvert \leqslant d_0) \wedge (y_1 - y_2 > d_0))$