2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Линейное упорядочивание точек
Сообщение11.09.2023, 19:05 


12/07/15
01/11/24
3276
г. Чехов
Задача не учебная, формулируется по практическим соображениям. Я сам не математик, поэтому прошу отнестись с пониманием. Ожидаю дополнительных вопросов.

Задача:
Две точки ($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))$

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

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение11.09.2023, 19:13 


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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение11.09.2023, 19:50 


12/07/15
01/11/24
3276
г. Чехов
wrest
Я прочитал тему по ссылке, но у меня мозг взрывается.

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

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


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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение11.09.2023, 20:49 


05/09/16
12023
Mihaylo в сообщении #1608838 писал(а):
моем случае смысл присутствует, но хотелось бы некоего приближения в оптимальности.

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение11.09.2023, 21:06 


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

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение11.09.2023, 21:57 


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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение11.09.2023, 22:13 


05/09/16
12023
Mihaylo в сообщении #1608843 писал(а):
Наверное важны моменты, когда интервалы стремятся к бесконечно малым величинам.

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение12.09.2023, 01:54 


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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение12.09.2023, 17:38 


12/07/15
01/11/24
3276
г. Чехов
Sender в сообщении #1608845 писал(а):
непрерывного взаимно однозначного отображения прямоугольника на прямую?

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

-- 12.09.2023, 17:47 --

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

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

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение12.09.2023, 20:59 


12/07/15
01/11/24
3276
г. Чехов
Я тут подумал и понял, что можно уточнить задачу: точки $(x_1, y_1)$ и $(x_2, y_2)$ произвольны, но расстояние между ними не меньше некоторого конечного расстояния $d$. Если точки близко расположены, то смысл такого выбора точек теряется.

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение13.09.2023, 18:14 


12/07/15
01/11/24
3276
г. Чехов
Придумал метод триангуляции. Измеряем расстояние между точками $(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}))$

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение14.09.2023, 19:42 


12/07/15
01/11/24
3276
г. Чехов
Нашел более простую функцию упорядочивания.
Самую первую функцию упорядочивания в декартовых координатах можно переписать следующим образом:
$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$.

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение17.09.2023, 20:15 


12/07/15
01/11/24
3276
г. Чехов
Свойством транзитивности такое сравнение двух точек не обладает (есть простой контрпример). Поэтому применить алгоритмы сортировки невозможно. Наверное все ждали подобное резюме. :lol:

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

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение18.09.2023, 01:59 
Заслуженный участник


31/12/05
1516
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$?

 Профиль  
                  
 
 Re: Линейное упорядочивание точек
Сообщение18.09.2023, 06:55 


12/07/15
01/11/24
3276
г. Чехов
:oops: :oops: :oops:
Извиняюсь, следовало написать так:

$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))$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group