2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Расположение точек на сфере
Сообщение21.07.2018, 20:41 


28/11/17
5
Есть задача: расположить равноудалёно друг от друга 12 точек на полусфере.
Т.к. правильного многогранника удовлетворяющего данном условию не существует, есть только приближенное решение в виде следующей фигуры: https://en.wikipedia.org/wiki/Snub_cube. Решение задачи с учетом граничных условий на границе полусферы (на большом круге) на данном этапе опускается, поэтому решение можно считать подходящим.

Однако появился интерес вывести аналитическое решение, поэтому перефразирую вопрос: составление формулы для нахождения расположения равноудаленных друг от друга N точек на сфере. Ответ хотелось бы получить, например, в виде расстояния между точками.

Пока что есть некоторые наработки, но до конца далековато. Есть две идеи, как составить решение

1. Через физический смысл задачи. Точки - отталкивающиеся заряды. Тогда можно взять формулу для расстояния по дуге между двумя точками, загнать её в суперпозицию сил отталкивания всех точек в виде ряда, и найти общую энергию системы. По идее условию равноудалёности будет соответствовать минимальная потенциальная энергия системы.

2. Через математику. Начало тоже самое, однако остановиться на суперпозиции расстояния всех точек и наложить ограничение на расстояние между точками (оно должно быть минимально?)

Буду рад Вашим замечаниям, советам, формулам.

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


09/09/14
6328
firstround в сообщении #1328125 писал(а):
Есть задача: расположить равноудалёно друг от друга 12 точек на полусфере.
Т.к. правильного многогранника удовлетворяющего данном условию не существует, есть только приближенное решение в виде следующей фигуры
А чем просто правильный двенадцатиугольник на большой окружности не устроит? Можете сформулировать вопрос так, чтобы было понятно, чем предложенный курносый куб лучше правильного многоугольника или хотя бы ромбокубооктаэдра?

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


13/08/08
14451
Что значит "равноудалённые друг от друга"? В какой метрике? В трёхмерном пространстве с евклидовой метрикой так можно расположить только 4 точки — в вершинах правильного тетраэдра. Или тут что-то иное?

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение21.07.2018, 20:59 
Заслуженный участник


20/08/14
11177
Россия, Москва
Насколько я знаю задача в общем виде не решена. Более того, не решена даже для многих достаточно малых $N$, типа 5, 9, 11 и т.д. (тут могу и ошибаться, ну да, про 5 и ошибся, в 2010 доказали).
Тупой поиск в гугле по названию темы даёт сразу две относительно полезных ссылки:
http://www.mathnet.ru/php/archive.phtml ... n_lang=rus
https://www.fundamental-research.ru/ru/ ... w?id=31243
Из последней по [13] и ещё одним шагом попадаем в:
http://mathworld.wolfram.com/ThomsonProblem.html
После этого уже можно и вики глянуть: Проблема Томсона.

Так же рекомендую уже существующую тему на этом форуме: «N точечных зарядов на поверхности сферы»

В общем стоит начать с изучения литературы и уже известных решений и методов.

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение21.07.2018, 21:05 


28/11/17
5
grizzly в сообщении #1328127 писал(а):
А чем просто правильный двенадцатиугольник на большой окружности не устроит? Можете сформулировать вопрос так, чтобы было понятно, чем предложенный курносый куб лучше правильного многоугольника или хотя бы ромбокубооктаэдра?
Такая система не устойчива, точки при отталкивании будут пытаться уйти в сторону с большого круга (перпендикулярно его окружности). Не могу сформулировать вопрос через расстояния, пусть пока будет так. Вообще оригинал задачи звучит скорее как "равномерное заполнение всей поверхности сферы"

Мммм, наверно Snub не лучше ромбокубооктаэдра, второе тоже подойдёт.

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение21.07.2018, 23:33 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
firstround, не могу понять. В стартовом сообщении у вас упомянута полусфера. Т., о., ваша проблема это вовсе не проблема Томсона, а лишь схожая с ней. Но тогда при чём здесь курносый куб и прочее, они же явно не подходят.

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 01:23 


28/11/17
5
gris в сообщении #1328128 писал(а):
Что значит "равноудалённые друг от друга"? В какой метрике? В трёхмерном пространстве с евклидовой метрикой так можно расположить только 4 точки — в вершинах правильного тетраэдра. Или тут что-то иное?


По типу правильных многогранников. https://en.wikipedia.org/wiki/Thomson_problem
Если говорить о зарядах, то расположить их так, чтобы система была устойчивой.

Dmitriy40 в сообщении #1328129 писал(а):
Насколько я знаю задача в общем виде не решена. Более того, не решена даже для многих достаточно малых $N$, типа 5, 9, 11 и т.д. (тут могу и ошибаться, ну да, про 5 и ошибся, в 2010 доказали).
Тупой поиск в гугле по названию темы даёт сразу две относительно полезных ссылки:
http://www.mathnet.ru/php/archive.phtml ... n_lang=rus
https://www.fundamental-research.ru/ru/ ... w?id=31243
Из последней по [13] и ещё одним шагом попадаем в:
http://mathworld.wolfram.com/ThomsonProblem.html
После этого уже можно и вики глянуть: Проблема Томсона.

Так же рекомендую уже существующую тему на этом форуме: «N точечных зарядов на поверхности сферы»

В общем стоит начать с изучения литературы и уже известных решений и методов.



Вот спасибо, проблему Томсона видел, оттуда и взял приближенное решение, хочется понять, как его получили, ведь там расчет до фигур с 470 вершинами. Статьи гляну и на днях отпишусь, спасибо еще раз.

Aritaborian в сообщении #1328145 писал(а):
firstround, не могу понять. В стартовом сообщении у вас упомянута полусфера. Т., о., ваша проблема это вовсе не проблема Томсона, а лишь схожая с ней. Но тогда при чём здесь курносый куб и прочее, они же явно не подходят.


"Стартовая" задача действительно о полусфере, но это лишь частный случай более полной задаче, которую и хочется решить. Решишь задачу о всей сфере в общем виде - решишь задачу хоть о секторе, просто добавив граничных условий.

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 08:29 
Аватара пользователя


26/05/12
1534
приходит весна?
Dmitriy40 в сообщении #1328129 писал(а):
Более того, не решена даже для многих достаточно малых $N$, типа 5, 9, 11 и т.д.
Вот такое решение не подойдёт для девяти точек?

(Оффтоп)

Изображение


gris в сообщении #1328128 писал(а):
Что значит "равноудалённые друг от друга"? В какой метрике?
Очевидно, метрика Евклидова на сфере (длина дуги). А равноудалённость наверняка понимается в смысле "минимальное расстояние между двумя точками максимально". Во всяком случае именно такая минимаксная задача приводит к правильным многогранникам в случае удачного числа точек. В случае же неудачного числа всё может быть на столько плохо, что даже нет единственного решения: свободные точки "болтаются" в полостях между другими "связанными" точками. Такой неоднозначности не возникает в задаче Томпсона (так как там потенциальная энергия является гладкой функцией, и даже когда минимум не единственнен, он является локально единственным).

-- 22.07.2018, 08:47 --

firstround в сообщении #1328125 писал(а):
Однако появился интерес вывести аналитическое решение
Думаю, гиблое дело. То есть, если аналитическое решение представить в виде "вот уравнение-крокодил и у него есть корень вот на таком отрезке, который и является ответом", то что-то ещё, наверное, можно придумать. А вот выразить это число в радикалах точно не получится. Такое делается только численно.

-- 22.07.2018, 08:57 --

firstround в сообщении #1328151 писал(а):
"Стартовая" задача действительно о полусфере, но это лишь частный случай более полной задаче, которую и хочется решить.
Знаете, решать задачу на сфере значительно более приятно (читай: проще) именно потому, что у этого пространства нет границы (в отличие от полусферы) и симметрия значительно выше. Так что это на мой взгляд две совершенно разные задачи, хоть постановка у них отличается всего лишь допустимой областью размещения.

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


13/08/08
14451
B@R5uk, спасибо. Просто у того, кто не в теме, может возникать душевная боль по поводу равноудалённости "друг от друга". Попарная? Не то. Или равноудалённость каждой точки от множества остальных точек? Тут подобие возникает. Ваше объяснение внесло успокоение :cry:

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 15:19 
Аватара пользователя


26/05/12
1534
приходит весна?
Dmitriy40 в сообщении #1328129 писал(а):
Более того, не решена даже для многих достаточно малых $N$, типа 5, 9, 11 и т.д.
Если всё-таки имеется в виду полусфера, то я как-то высчитал вот такие две фигуры:

Изображение Изображение


Если их правильно разрезать на две части плоскостью (точки 1-2-10-12-4 для первой и 1-8-14-15-9 или 1-6-16-17-7 для второй), то как раз получится ответ для 9 и 11 точек. Эти две фигуры являются наиболее "просторным" размещением 13 и 17 точек на сфере, при этом меньшее число точек (12 и 16) не позволяет разрезать сферу нужным образом (чтобы "рёбра жёсткости" упирались в границу и было нужное число точек). То, что мне не удалось найти ещё более "просторное" размещение, ещё, конечно, не доказательство решения, но, на мой взгляд, эти фигуры хорошие кандидаты в решение.

Кстати, как в таких случаях доказывается, что другого, более лучшего решения нет?

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 15:22 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
B@R5uk, не поделитесь немножко подробностями? Какие инструменты использовали для отыскания решения и визуализации?

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 15:39 
Аватара пользователя


26/05/12
1534
приходит весна?
Aritaborian, всё делал в Матлабе: и решение и визуализацию. Сначала набрасывал на сферу нужное число точек и растряхивал их методом Монте-Карло (с постепенным снижением температуры). После того, как мне становилась понятна структура и симметрия получающейся фигуры, я для каждой фигуры задавал одну-две-три варьируемых переменных (задающих неполную фигуру) и с помощью функции fminsearch находил искомое.

Например, для 11-и точек достаточно задать длину ребра и, пляша от точки 1, получить координаты всех остальных точек в силу симметрии фигуры (полярные углы фиксированы), после чего делается оптимизация расстояния между точками 10 и 11. В случае 16-и точек чуть сложнее: нужны длина ребра и одна полярная координата, чтобы задать положение точек 2—5. На их основе строятся остальные точки и оптимизируется расположение самых верхних точек (14—17).

-- 22.07.2018, 15:49 --

B@R5uk в сообщении #1328160 писал(а):
Во всяком случае именно такая минимаксная задача приводит к правильным многогранникам в случае удачного числа точек.
Я тут чуть-чуть покривил душой, так как в случае 8-и точек ответом будет не куб, а вот такая фигура:
Изображение

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 16:09 


28/11/17
5
B@R5uk в сообщении #1328160 писал(а):
Вот такое решение не подойдёт для девяти точек?


Вы взяли Трижды наращённую треугольную призму? Да, подойдет, примерно в том направлении и пытаюсь думать, с той лишь разницей, что решения для фигур с большим количеством вершин будут содержать разные расстояния между соседними точками (например грани квадраты и треугольники, тогда расстояние по диагонали квадрата будет больше, чем расстояние по его стороне, а задачу на данный момент могу сформулировать лишь с одной переменной L)

B@R5uk в сообщении #1328160 писал(а):
Думаю, гиблое дело. То есть, если аналитическое решение представить в виде "вот уравнение-крокодил и у него есть корень вот на таком отрезке, который и является ответом", то что-то ещё, наверное, можно придумать. А вот выразить это число в радикалах точно не получится. Такое делается только численно.


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


B@R5uk в сообщении #1328160 писал(а):
Очевидно, метрика Евклидова на сфере (длина дуги). А равноудалённость наверняка понимается в смысле "минимальное расстояние между двумя точками максимально". Во всяком случае именно такая минимаксная задача приводит к правильным многогранникам в случае удачного числа точек. В случае же неудачного числа всё может быть на столько плохо, что даже нет единственного решения: свободные точки "болтаются" в полостях между другими "связанными" точками. Такой неоднозначности не возникает в задаче Томпсона (так как там потенциальная энергия является гладкой функцией, и даже когда минимум не единственнен, он является локально единственным).


В чем разница между "минимаксной задачей" и задачей Томпсона? Вам известны какие-нибудь материалы по решению задачи Томпсона?

B@R5uk в сообщении #1328160 писал(а):
Знаете, решать задачу на сфере значительно более приятно (читай: проще) именно потому, что у этого пространства нет границы (в отличие от полусферы) и симметрия значительно выше. Так что это на мой взгляд две совершенно разные задачи, хоть постановка у них отличается всего лишь допустимой областью размещения.


Что сложнее, это понятно, я к тому, что задача о полусфере лишь следующий этап решения задачи о сфере, как бы продолжение, для которого нужно сначала разобраться с общим случаем распределения зарядов на сфере.

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 17:49 


07/11/12
135
B@R5uk в сообщении #1328160 писал(а):
Я тут чуть-чуть покривил душой, так как в случае 8-и точек ответом будет не куб, а вот такая фигура:
Изображение

Это называется - 4-антипризма из семейства n-антипризм, которые иногда включают в класс архимедовых многогранников (вместе с обычными n-призмами).

 Профиль  
                  
 
 Re: Расположение точек на сфере
Сообщение22.07.2018, 18:20 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
B@R5uk, спасибо.

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

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



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

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


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

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