2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 точки на окружности
Сообщение24.10.2015, 23:54 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Есть $n$ случайных точек на окружности. И есть равномерная сетка из $m$ узлов ($m>n$) с нефиксированным началом (можно вращать).
Точки необходимо распределить по сетке "оптимальным образом" (в одном узле сетки не более одной точки). Интересует соответствующий угол поворота сетки и номера узлов для каждой точки.
Под "оптимальностью" понимается, например, сумма квадратов отклонений точки от соответствующего узла.
$n$ и $m$ порядка 10-100.

Понятно, что можно "тупо" перебрать все варианты назначения точкам узлов - это потребует решить $C_{m-1}^{n-1}$ раз уравнение для (оптимального) угла поворота.

Как сделать лучше?

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 00:39 
Заслуженный участник
Аватара пользователя


15/10/08
11536
$m$ подбирается по распределению $n$ или фиксировано?

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 00:46 
Заслуженный участник


26/05/14
981
Geen в сообщении #1066359 писал(а):
Точки необходимо распределить по сетке "оптимальным образом" (в одном узле сетки не более одной точки).


Это условие не вполне ясно. Как именно точки отображаются в узлы решётки? Если отображаются в ближайший узел, то не будет инъективности.

-- 25.10.2015, 00:51 --

Geen в сообщении #1066359 писал(а):
Под "оптимальностью" понимается, например, сумма квадратов отклонений точки от соответствующего узла.


Квадраты евклидовых расстояний или квадраты углов?

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


15/10/08
11536
slavav в сообщении #1066382 писал(а):
Как именно точки отображаются в узлы решётки?
Geen в сообщении #1066359 писал(а):
в одном узле сетки не более одной точки
Вероятно здесь имелись в виду не узлы, а ячейки.

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 12:20 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Утундрий в сообщении #1066379 писал(а):
$m$ подбирается по распределению $n$ или фиксировано?

Фиксировано.

-- 25.10.2015, 12:21 --

Утундрий в сообщении #1066387 писал(а):
Вероятно здесь имелись в виду не узлы, а ячейки.

Да, возможно правильнее сказать ячейки.

-- 25.10.2015, 12:24 --

slavav в сообщении #1066382 писал(а):
Квадраты евклидовых расстояний или квадраты углов?

Меру можно поменять (в рамках разумного) если это упростит алгоритм. Исходно я рассматриваю углы.

-- 25.10.2015, 12:26 --

slavav в сообщении #1066382 писал(а):
Если отображаются в ближайший узел, то не будет инъективности.

Можно сказать, что отображаются в ближайший не занятый (если отображать "по очереди").

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 12:31 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Всё равно непонятно. Допустим, точки почти слиплись и попадают целиком в одну ячейку. Каково будет оптимальное положение сетки для такого случая?

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 12:38 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Ну, допустим, у нас три точки и все "на одном угле". А ячеек/узлов у нас 5. Тогда "правильное" распределение будет $-1,0,1$ и узел $0$ ориентирован на точки.
(Понятно, что нумерацию узлов можно циклически менять, т.е. мы всегда будем иметь $m$ равнозначных решений)

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 12:59 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Geen в сообщении #1066496 писал(а):
распределение будет $-1,0,1$

Что это значит?

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 13:21 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Утундрий в сообщении #1066504 писал(а):
Geen в сообщении #1066496 писал(а):
распределение будет $-1,0,1$

Что это значит?

Три точки распределяются в три соседние ячейки. Или точкам приписываются номера трёх последовательных узлов.

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 14:17 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Если тчки можно так лихо "распрелелять" по ячейкам, то я не вижу задачи. Просто "распределите" их как душе будет угодно.

 Профиль  
                  
 
 Re: точки на окружности
Сообщение25.10.2015, 15:26 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Утундрий в сообщении #1066540 писал(а):
Если тчки можно так лихо "распрелелять" по ячейкам, то я не вижу задачи. Просто "распределите" их как душе будет угодно.

Надо минимизировать сумму квадратов отклонений (разниц между "приписанным" направлением и реальным)

 Профиль  
                  
 
 Re: точки на окружности
Сообщение26.10.2015, 00:02 
Заслуженный участник


26/05/14
981
Идея такая: надо показать что оптимальное отображение точек в номера ячеек монотонно. Понятие монотонности, конечно нужно определить точно для этой задачи. Полагаю для квадратов углов монотонность можно показать сравнительно легко. Для квадратов евклидова расстояния ситуация сложнее: можно доказать что если отображение оптимально и при отображении все точки смещаются на углы меньше $\pi/2$, то отображение монотонно.

 Профиль  
                  
 
 Re: точки на окружности
Сообщение26.10.2015, 00:19 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Мне кажется, что всё несколько проще. Перед нами, по сути, задача минимизации периодической функции одной переменной.

 Профиль  
                  
 
 Re: точки на окружности
Сообщение26.10.2015, 00:35 
Заслуженный участник


26/05/14
981
Утундрий в сообщении #1066937 писал(а):
Мне кажется, что всё несколько проще. Перед нами, по сути, задача минимизации периодической функции одной переменной.


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

 Профиль  
                  
 
 Re: точки на окружности
Сообщение26.10.2015, 00:40 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Утундрий в сообщении #1066937 писал(а):
Мне кажется, что всё несколько проще. Перед нами, по сути, задача минимизации периодической функции одной переменной.

Да, но у неё очень много локальных минимумов.... ($C_m^n$, вообще говоря).

slavav в сообщении #1066922 писал(а):
Для квадратов евклидова расстояния ситуация сложнее

Нам не надо сложнее :-)

-- 26.10.2015, 00:48 --

slavav в сообщении #1066945 писал(а):
Да, после того как вы выбрали отображение из точек в ячейки, надо оптимизировать некую функцию поворачивая ячейки.

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

-- 26.10.2015, 01:08 --

Пока нашёл такое "приближение к решению"...
Упорядочим точки по углу и найдём разницу между соседними ($n$ разниц). Перенумеруем эти "промежутки" по убыванию ($da_1,da_2,....$).
Пусть $k=m-n$ - кол-во (пустых) ячеек, которые нам нужно "добавить".
Первую ячейку добавляем в наибольший промежуток ($da_1$).
Для второй ячейки смотрим что больше - $da_1/3$ или $da_2/2$. Где больше, туда и добавляем.... Далее - "аналогично" (могу привести код в C++ или MatLab).
Не знаю только является ли это решением.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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