Шарики, ниточки...

[Circiter]

Здравствуйте. Уже в течении года или двух я периодически возвращаюсь к одной, на мой взгляд интересной, задаче, однако решить её мне не удается. Эта задачка несколько раз возникала при совершенно казалось бы различных обстоятельствах. Однажды я даже наткнулся на похожую по смыслу задачу в интернете, но, во-первых, ссылку потерял; а во-вторых, о той задаче говорилось как о нерешенной проблемке.

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

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

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

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

Заранее благодарю за ваши ответы.


Post scriptum.

Своего вклада, как такового, пока нет, могу только предложить такую конструкцию. Пусть имеется метрическое пространство $(\mathbb{V},\ \rho:\mathbb{V}\times\mathbb{V}\to\mathbb{R})$ и набор из $n$ "точек" (центров шаров) $\xi_1,\ \ldots,\ \xi_n$, $\xi_i\in\mathbb{V}$. Тогда вопрос задачи сводится к вопросу о разрешимости системы неравенств $\alpha<\rho(\xi_i,\ \xi_j)<\beta,\ i\neq j$, где $\alpha$ -- число, характеризующее радиус шариков (например можно положить $\alpha=2$, хотя, думаю, другие разумные значения не повредят общности); а $\beta$ -- число, характеризующее длину нитей (в данном случае это просто расстояние между центрами шаров). Особо интересен случай когда в качестве $\mathbb{V}$ выбрано $\mathbb{R}^2$ с обычной евклидовой метрикой. А вот как решать такие неравенства, я не знаю. В этом и проблема...

[gris]

Circiter писал(а):

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

Какой системы? Вы её не описали.
Если система уже задана, то достаточно проверить все неравенства, а не решать их.

Решать неравенства нужно в такой задаче: Каково наибольшее число точек на плоскости образуют полное связное цирциттерово множество для заданных значений праметров. Кстати, там должны быть нестрогие неравенства.

Такие множества называются "цирциттеровы множества".
Обычно решаются задачи возможности добавления новой точки к цирциттерову множеству.
Множества, к которым нельзя добавить ни одной точки, называется "полным цирциттеровым"
Множества, у которых каждый шар касается по крайней мере ещё одного, называется связно-цирциттеровым.
Множество, где каждый шар касается всех остальных, называется плотно-цирциттеровым.
Где каждый шар находится строго на расстоянии $\alpha$ от каждого из оставшихся, по-моему регулярным.
Максимальное регулярное цирциттерово множество в $R^n$ состоит из $n+1$ точки.
Это очень интересная тема.

[Circiter]

2gris

Цитата:

Какой системы? Вы её не описали.

Я подразумевал тот самый набор шаров и ниток. Это --- система; при некоторых условиях утверждение о существовании такой системы может оказаться ложным. Хочется выяснить при каких.

Я понимаю, что задача дана мной несколько неформально, но я как-раз таки и надеюсь на получение более точных формулировок.

Цитата:

Такие множества называются "цирциттеровы множества".

О как это хорошо подходит к моему нику. Спасибо, буду копать в этом направлении, хотя ответ google'я под данному запросу меня напугал.

Цитата:

Кстати, там должны быть нестрогие неравенства

Да пожалуйста, я же говорю, у меня нет пока продуманной и точной формулировки.

Цитата:

Это очень интересная тема.

Да! Я на ней помешан!

-- Пн окт 05, 2009 22:12:37 --

Цитата:

Максимальное регулярное цирциттерово множество в $R^n$ состоит из $n+1$ точки.

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

Кстати, описанная мной система неравенств похожа на некоторый многомерный параллелепипед $\alpha\leq x^i_j\leq\beta$, это можно как-нибудь использовать?

[Circiter]

К сожалению, по наводке gris'а найти ничего не удалось...

Зато придумал (на самом деле просто выкинул нитки из условия) ещё одну комбинаторно-геометрическую интерпретацию критерия существования решений системы неравенств вида $\alpha<\rho(\xi_i,\ \xi_j)<\beta$. Решение существует если возможно разместить $n$ материальных шаров диаметра $\alpha$ внутри шара диаметра $\alpha+\beta$ (под диаметром здесь следует понимать всего-лишь удвоенный радиус). Кажется, в такой формулировке задача имеет какое-то отношение к наиплотнейшим упаковкам шаров, хотя именно наиплотнейшей упаковки здесь и не требуется...

Можно ли строить искомый критерий каким-либо образом анализируя соотношения объемов большого и малых шаров, или я в тупиковом направлении двигаюсь? Ещё раз спасибо за ваши ответы.

P.S.: Вот для систем линейных уравнений критерием разрешимости является неравенство детерминанта матрицы системы нулю. Мне бы тоже какое-нибудь подобное правило найти, только для систем интересующих меня неравенств.

[gris]

Circiter, если посмотреть Ваши посты в других разделах, то создаётся впечатление, что здесь Вы немного дурачитесь
Хотя подобные задачи очень хороши для школьного кружка. Именно в терминах шариков-ниточек. Ну а из школьных по виду задач часто вырастают вполне диссертабельные темы. Так что пилите трясите исследуйте.
Если честно, то мне понравилось. Я составил несколько красивых цирциттеровых множеств на плоскости.

[Circiter]

2gris
Так где вы слышали о цирциттеровых множествах? Назовите, пожалуйста, хотя бы один источник.

Цитата:

Я составил несколько красивых цирциттеровых множеств на плоскости.

Вы руководствовались каким-то алгоритмом, или угадывали структуру? Я вот для себя программульку накалякал, рисующую подобные диаграммки. Вроде работает (минимизирует расстояние $\beta$ с учетом ограничений по $\alpha$), но как-то ненадежно все-это... Хочется аналитический подход разработать (если его конечно ещё нет ).

Цитата:

Так что пилите трясите исследуйте.

Бум. Спасибо за поддержку.

[gris]

Circiter
То есть меня Вы за источник вовсе даже совсем и не принимаете :обиделся:?

Я просто баловался с окружностями, вернее с кольцами. Параметры $\alpha$ и $\beta$ задают кольцо вокруг точки. Точки цирциттерова множества обладают тем свойством, что каждая лежит в непустом пересечении всех колец.
Я всё-таки до сих пор не понимаю, в чём состоит Ваша задача.
Я вижу несколько формулировок.
1) Заданы несколько точек. Надо определить минимальное $\alpha$ и максимальное $\beta$ при котором данное множество будет цирциттеровым. Легко проверить, что если множество является цирциттеровым с некоторыми значениями параметров $\alpha$ и $\beta$, то оно останется цирциттеровым при уменьшении $\alpha$ и увеличении $\beta$
2) Проверить, является ли множество точек цирциттеровым с данными параметрами? Ну тут просто тупо проверить выполнение условий и всё.
3) Самое интересное и доступное даже школьникам. Строить различные (полные, регулярные, связные, плотные, и т.д.) цирциттеровы множества из заданного количества точек.

[Circiter]

Цитата:

То есть меня Вы за источник вовсе даже совсем и не принимаете :обиделся:?

Сорри. Но все-таки откуда-то словечко это должно же было взяться (цирциттерово)? Или у вас юмор такой?

Просто допустим, мне захочется ещё где-нибудь ляпнуть о своих изысканиях. Упомяну цирциттеровы множества, а на что сослаться? На форумный пост? На статейку/книжку, согласитесь, как-то привычнее. Или хотя-бы фамилию/инициалы назовите (ваши).

Цитата:

Я вижу несколько формулировок.
...
1) ...
2) ..
3) Самое интересное и доступное даже школьникам. Строить различные (полные, регулярные, связные, плотные, и т.д.) цирциттеровы множества из заданного количества точек.

Кажется, именно это; да даже не строить, а просто сказать можно или нет построить. Но я не уверен, что это доступно буквально каждому школьнику.

Давайте я немножко уточню задачу (по-сути повторю условия). Итак, исходные данные -- три числа, т.е. $\alpha$, $\beta$ ($\alpha<\beta$) и $n$, а также какое-нибудь пространство $\mathbb{V}$ с функцией расстояния $\rho(\cdot,\cdot)$. Далее возможны две эквивалентные (?) формулировки-утверждения:

1. Утверждение: $\exists\ \mathcal{C}=\{\xi_i\}_{i=1}^n\subset\mathbb{V}\ |\ (\forall\ a,b\in\mathcal{C}\land a\neq b\ \rho(a,\ b)\in]\alpha,\beta[).$
   Т.е. утверждается существование набора $n$ точек с попарными расстояниями (между точками), лежащими в интервале $]\alpha,\beta[$.
   
2. Пусть $\mathbb{B}(x,\ r)\equiv\{a\in\mathbb{V}\ |\ \rho(x,\ a)<r\}$ (открытый шар в $\mathbb{V}$ с центром $x$ и радиусом $r$). Утверждение: $\exists\ \mathcal{C}=\{\xi_i\}_{i=1}^n\subset\mathbb{V}\ |\ (\forall\ a\in\mathcal{C}\ \mathbb{B}(a,\ 0,5\alpha)\subset\mathbb{B}(0,\ \frac{\alpha+\beta}{2}))\land$
   $\land(\forall\ a,b\in\mathcal{C}\land a\neq b\ \mathbb{B}(a,\ 0,5\alpha)\cap\mathbb{B}(b,\ 0,5\alpha)=\varnothing).$
   Т.е. утверждается возможность разместить $n$ материальных шаров диаметра $\alpha$ полностью внутри сферы диаметра $\alpha+\beta$.

(Прошу прощения за криво написанные логические формулы )

Примечание: все элементы $\mathcal{C}$ различны.
Вопрос задачи: чему равно логическое значение Утверждения?
Расширение задачи: максимизировать $n$.
Указание: можно ограничиться евклидовым пространством.


Как уже было сказано выше, я пытался использовать именно вторую формулировку, анализирую отношения объемов шаров. Но с этой стороны к задаче тоже подступиться не удалось. Во-первых, формулы для объемов сильно усложняются с ростом размерности пространства; а во-вторых, в пространствах большой размерности промежутки между малыми шарами становятся слишком большими, т.е. суммарный объем промежутков способен вместить в себя ещё большее количество таких шаров.

В $\mathbb{R}^2$ можно попробовать разместить малые шары в узлах гексагональной решетки и посмотреть, сколько влезет в большой шар... Но это неуниверсальное решение... Действительно, что если размерность пространства $>24$, довольствоваться грубыми оценками?

Но мне кажется, что настоящая задача все-таки гораздо проще проблемы наиплотнейших сферических упаковок... Кстати, меня особо интересует по ряду причин именно случай $\alpha=2$, $\beta=4$.

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

[gris]

Вот уж не поверю, что Вы не слышали о цирциттеровости. Circiter в переводе с латинского - рядом, близко, вокруг. Вы ник свой взяли, вероятно, именно поэтому. В честь цирциттеровых множеств. Или я ошибаюсь?
Если честно, то меня хватает только на обычную плоскость, хотя самое интересное, конечно, начинается в гильбертовом пространстве.
Кстати, цирциттеровость очень хорошо применяется в физике атомного ядра при описании сильных взаимодействий, но тут уж я ничего не могу сказать толкового. Задачи на плоскости я решаю до сих пор. Накоплю побольше результатов - обязательно покажу. Но у меня всё на школьном уровне :скромно:

[Профессор Снэйп]

Circiter в сообщении #250944 писал(а):

Цитата:

То есть меня Вы за источник вовсе даже совсем и не принимаете :обиделся:?

Сорри. Но все-таки откуда-то словечко это должно же было взяться (цирциттерово)? Или у вас юмор такой?

Можно, наверное, сказать, что и юмор. Gris просто образовал термин от Вашего ника

[gris]

Отнюдь, многоуважаемый Профессор Снэйп! Ровно наоборот.

Circiter, признавайтесь, откуда у Вас такой ник. Не в честь же попа! Хотя не по правилам ники обсуждать, но интересно.

[Circiter]

2gris

Цитата:

Вы ник свой взяли, вероятно, именно поэтому. В честь цирциттеровых множеств. Или я ошибаюсь?

Совпадение.

Цитата:

признавайтесь, откуда у Вас такой ник

Страсть к приближенным вычислениям.

Цитата:

Кстати, цирциттеровость очень хорошо применяется в физике атомного ядра при описании сильных взаимодействий

Хм, ну да, шарики с ниточками -- суть упрощенная модель конфайнмента из хромодинамики.

2Профессор Снэйп

Цитата:

Gris просто образовал термин от Вашего ника

Похоже на историю о термине энтропия.

[gris]

Circiter, хотел бы уточнить, вернувшись к шарикам и ниточкам.
Случай $\alpha=2$ и $\beta=4$ означает, что каждая точка окружена непроницаемой оболочкой радиуса $\alpha/2=1$, а длина ниточки - $4$.
Правильно?

[Circiter]

2gris

Цитата:

Случай $\alpha=2$ и $\beta=4$ означает, что каждая точка окружена непроницаемой оболочкой радиуса $\alpha/2=1$, а длина ниточки - $4$.
Правильно?

Совершенно верно ("ниточки" соединяют сами точки, т.е. центры непроницаемых единичных сфер-оболочек). Более того, можно рассмотреть лишь евклидовы пространства малой размерности (e.g. $\mathbb{R}^2$, $\mathbb{R}^3$).

-- Вт окт 13, 2009 23:01:04 --

Предположение 1. Кажется, формулировки 1 и 2 вовсе не эквивалентны (я занизил оценку диаметра $\alpha+\beta$, правильная оценка как-то связана с -- в вашей терминологии -- понятием максимального регулярного цирциттерова множества).
Предположение 2. Исходную задачу в общей постановке (или хотя-бы для $R^m$, но с максимизацией $n$) решить аналитически современная математика, кажется, пока не может.

[Someone]

Но "ниточки" при необходимости сквозь сферы проходят, а не огибают их?