2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Поместить шары в минимальную сферу
Сообщение20.04.2019, 12:41 


16/04/19
161
Задан набор шаров $(x_i, y_i, z_i, R_i)$. Требуется найти сферу минимального радиуса, которая содержит заданные шары.

хотел в олимпиадные вбросить, промазал

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 14:23 
Заслуженный участник


20/08/14
11067
Россия, Москва
Начать с первого шара. Для каждого следующего проверять не внутри ли он уже накопленного, если нет - то увеличить и сместить накопленный. Получилось даже всего лишь $O(n)$.

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 16:17 
Заслуженный участник


23/07/08
10626
Crna Gora
Dmitriy40
Увеличить и сместить накопленный шар так, чтобы в него поместился очередной шар, несложно. А вот как его надо увеличить и сместить, чтобы ещё и обеспечить минимальность его радиуса на данном шаге?

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 17:30 


05/09/16
11468
Возможно, центр искомой сферы это центр масс точек-центров данных шаров $(x_i,y_i,z_i)$, у которых масса пропорциональна их радиусам $R_i$ (а не кубам радиусов).

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 17:49 
Заслуженный участник


27/04/09
28128
Понижение размерности и случай двух касающихся внешне окружностей не проваливает, а вот произвольную пару окружностей — уже, если я нигде не опечатался.

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 18:12 


05/09/16
11468
arseniiv
Да, не то я сказал.

-- 20.04.2019, 18:41 --

Википедия подсказывет [url]https://ru.wikipedia.org/wiki/Ограничивающая_сфера[/url] что простого ответа не будет даже в случае нулевых радиусов $R_i=0$

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 19:04 


16/04/19
161
wrest,
вроде решается за линейное время, в случае нулевых радиусов, по ссылке из той же википедии [Nimrod Megiddo. Linear-time algorithms for linear programming in R3 and related problems // SIAM Journal on Computing. — 1983. — Т. 12, вып. 4. — С. 759–776.]

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 19:15 


05/09/16
11468
feedinglight в сообщении #1388747 писал(а):
вроде решается за линейное время,

Дело не в том, что задача решается численными методами и за линейное (или квадратичное и т.п.) время можно найти ответ.
Во-первых, олимпиадная задача предполагает вывод какой-то неожиданно красивой\компактной формулы, чего тут помойму не ожидается. Но.. посмотрю что скажут другие, может интуиция тут меня подводит.
Во-вторых, предполагается, что автор темы знает ответ. А если НЕ знает, то тема должна быть в "помогите решить-разобраться" :mrgreen:

Или это для олиммиады по программированию? :roll:

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 19:33 


16/04/19
161
wrest
Решение знаю, но оно громоздкое.
Может быть не прав, но марафонские задачи тоже в этом разделе
Вообще, эта задача полезна для декомпозиции пространства (например, при поиске области контакта в контактных задачах механики), и, на мой взгляд, решение этой задачи в исходной или упрощённой формулировке вполне неожиданное и красивое.
Для не марафонской задачи по программированию подошла бы какая-то из упрощённых формулировок.

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 23:09 


23/02/12
3111
wrest в сообщении #1388749 писал(а):
feedinglight в сообщении #1388747 писал(а):
вроде решается за линейное время,

Дело не в том, что задача решается численными методами и за линейное (или квадратичное и т.п.) время можно найти ответ.
Во-первых, олимпиадная задача предполагает вывод какой-то неожиданно красивой\компактной формулы, чего тут помойму не ожидается.

Согласен с Вами. Здесь разговор идет не о решении задачи, а о нахождении алгоритма решения задачи, об оптимальности алгоритма в смысле минимума его сложности.
И вообще, так можно взять любую математическую статью и постановку задачи из нее использовать в качестве олимпиадной задачи. :-)

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 23:36 


16/04/19
161
ага, а ничё что куча "олимпиадных задач" решаются просто применением теоремы? мне показалась задача интересной
ладно, не нравится - ок, но не вижу кнопки "удалить тему"

просьба к модераторам удалить тему, а то слишком много "негатива"

 Профиль  
                  
 
 Re: Поместить шары в минимальную сферу
Сообщение20.04.2019, 23:38 
Заслуженный участник


23/07/08
10626
Crna Gora
Не надо удалять, мне нравится задача.

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

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



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

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


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

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