Поместить шары в минимальную сферу

[feedinglight]

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

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

[Dmitriy40]

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

[svv]

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

[wrest]

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

[arseniiv]

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

[wrest]

arseniiv
Да, не то я сказал.

-- 20.04.2019, 18:41 --

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

[feedinglight]

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

[wrest]

feedinglight в сообщении #1388747 писал(а):

вроде решается за линейное время,

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

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

[feedinglight]

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

[vicvolf]

wrest в сообщении #1388749 писал(а):

feedinglight в сообщении #1388747 писал(а):

вроде решается за линейное время,

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

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

[feedinglight]

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

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

[svv]

Не надо удалять, мне нравится задача.