точки на окружности

[Geen]

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

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

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

[Утундрий]

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

[slavav]

Geen в сообщении #1066359 писал(а):

Точки необходимо распределить по сетке "оптимальным образом" (в одном узле сетки не более одной точки).

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

-- 25.10.2015, 00:51 --

Geen в сообщении #1066359 писал(а):

Под "оптимальностью" понимается, например, сумма квадратов отклонений точки от соответствующего узла.

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

[Утундрий]

slavav в сообщении #1066382 писал(а):

Как именно точки отображаются в узлы решётки?

Geen в сообщении #1066359 писал(а):

в одном узле сетки не более одной точки

Вероятно здесь имелись в виду не узлы, а ячейки.

[Geen]

Утундрий в сообщении #1066379 писал(а):

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

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

-- 25.10.2015, 12:21 --

Утундрий в сообщении #1066387 писал(а):

Вероятно здесь имелись в виду не узлы, а ячейки.

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

-- 25.10.2015, 12:24 --

slavav в сообщении #1066382 писал(а):

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

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

-- 25.10.2015, 12:26 --

slavav в сообщении #1066382 писал(а):

Если отображаются в ближайший узел, то не будет инъективности.

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

[Утундрий]

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

[Geen]

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

[Утундрий]

Geen в сообщении #1066496 писал(а):

распределение будет $-1,0,1$

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

[Geen]

Утундрий в сообщении #1066504 писал(а):

Geen в сообщении #1066496 писал(а):

распределение будет $-1,0,1$

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

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

[Утундрий]

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

[Geen]

Утундрий в сообщении #1066540 писал(а):

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

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

[slavav]

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

[Утундрий]

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

[slavav]

Утундрий в сообщении #1066937 писал(а):

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

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

[Geen]

Утундрий в сообщении #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).
Не знаю только является ли это решением.