2014 dxdy logo

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

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




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

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

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

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 00:39 
Аватара пользователя
$m$ подбирается по распределению $n$ или фиксировано?

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 00:46 
Geen в сообщении #1066359 писал(а):
Точки необходимо распределить по сетке "оптимальным образом" (в одном узле сетки не более одной точки).


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

-- 25.10.2015, 00:51 --

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


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

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

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 12:20 
Аватара пользователя
Утундрий в сообщении #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 
Аватара пользователя
Всё равно непонятно. Допустим, точки почти слиплись и попадают целиком в одну ячейку. Каково будет оптимальное положение сетки для такого случая?

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

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 12:59 
Аватара пользователя
Geen в сообщении #1066496 писал(а):
распределение будет $-1,0,1$

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

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 13:21 
Аватара пользователя
Утундрий в сообщении #1066504 писал(а):
Geen в сообщении #1066496 писал(а):
распределение будет $-1,0,1$

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

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

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 14:17 
Аватара пользователя
Если тчки можно так лихо "распрелелять" по ячейкам, то я не вижу задачи. Просто "распределите" их как душе будет угодно.

 
 
 
 Re: точки на окружности
Сообщение25.10.2015, 15:26 
Аватара пользователя
Утундрий в сообщении #1066540 писал(а):
Если тчки можно так лихо "распрелелять" по ячейкам, то я не вижу задачи. Просто "распределите" их как душе будет угодно.

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

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

 
 
 
 Re: точки на окружности
Сообщение26.10.2015, 00:19 
Аватара пользователя
Мне кажется, что всё несколько проще. Перед нами, по сути, задача минимизации периодической функции одной переменной.

 
 
 
 Re: точки на окружности
Сообщение26.10.2015, 00:35 
Утундрий в сообщении #1066937 писал(а):
Мне кажется, что всё несколько проще. Перед нами, по сути, задача минимизации периодической функции одной переменной.


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

 
 
 
 Re: точки на окружности
Сообщение26.10.2015, 00:40 
Аватара пользователя
Утундрий в сообщении #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 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group