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  След.

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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