2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Вопрос про размерность
Сообщение15.05.2015, 17:18 
Аватара пользователя
Мне интересен следующий вопрос.

Есть $n$-мерный куб (или даже не куб, а всё $n$-мерное пространство, как удобнее).
Он разбит на достаточно большое (может быть, очень большое) количество областей неправильной формы.

Можно наложить любые естественные условия: например, что области не могут сильно отличаться по диаметрам, грубо говоря, диаметр одной области не может быть в сто раз больше диаметра другой. Или любое другое условие подобного вида, если оно поможет решить задачу. Например, если $n=2$, допустимы стандартные замощения квадратами, шестиугольниками (вдали от границы квадрата), и т.д.

Дальше составляется граф: каждой области ставится в соответствие вершина графа, если две области соседствуют, то соответствующие вершины соединяются ребром.

И вот вопрос: можно ли, имея этот граф, определить или оценить размерность $n$?

Например, мы видим, что каждая или почти каждая вершина графа имеет шесть соседних. Можно ли как-нибудь понять, что изображает этот граф: то ли разбиение куба на маленькие кубы, то ли разбиение двумерной фигуры на шестиугольники, по принципу правильного шестиугольного паркета?

Можно представить себе, что есть мир, разбитый на страны. Мы знаем в точности, какие страны соседние. Можно ли что-то сказать о размерности этого мира?

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

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:42 
Аватара пользователя
Тупо берём и строим вокруг какой-нибудь одной вершины вторую координационную сферу, третью и т.д. И вот если их можно построить достаточно много, чтобы на глаз стало видно некое подобие асимптотики, то - - -

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:45 
Аватара пользователя
Narn, расскажите подробнее, пожалуйста. Что значит "для любого набора областей сообщу, пусто их пересечение или нет"?
Граф как раз и показывает, какие области соприкасаются частью границы, какие нет.

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:49 
Аватара пользователя
Mikhail_K в сообщении #1015553 писал(а):
И вот вопрос: можно ли, имея этот граф, определить или оценить размерность $n$?
В такой формулировке, как у Вас, вряд ли что-то разумное можно сказать.

Но аналогичная характеристика размерности существует: П. С. Александров, Б. А. Пасынков. Введение в теорию размерности."Наука", Москва, 1973. Глава 2, § 2.

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:49 
Аватара пользователя
Сдаётся мне, ответ может быть лишь стохастический. Причём, сильно зависящий от допустимой степени разноразмерности, шестиугольности квадратов и прочих подобного рода штук.

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:53 
Ну, я об открытых покрытиях думаю. Пусть $\{U_i\}$ --- такое покрытие. Ваш граф всего лишь говорит мне, верно ли, что $U_i \cap U_j$ пусто. А вот про тройки $U_i \cap U_j \cap U_k$, четверки, и прочие он уже никакой информации не содержит.

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:56 
Аватара пользователя
Someone в сообщении #1015573 писал(а):
В такой формулировке, как у Вас, вряд ли что-то разумное можно сказать.

Но аналогичная характеристика размерности существует: П. С. Александров, Б. А. Пасынков. Введение в теорию размерности."Наука", Москва, 1973. Глава 2, § 2.


На своей формулировке не настаиваю, можно её варьировать.
Книгу посмотрю.

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:57 
Аватара пользователя
Narn
Вот зачем вы инцидентность на пересечение заменили, а?

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 18:00 
Аватара пользователя
Narn в сообщении #1015579 писал(а):
Ну, я об открытых покрытиях думаю. Пусть $\{U_i\}$ --- такое покрытие. Ваш граф всего лишь говорит мне, верно ли, что $U_i \cap U_j$ пусто. А вот про тройки $U_i \cap U_j \cap U_k$, четверки, и прочие он уже никакой информации не содержит.


Прекрасно! Пусть известно всё что надо про тройки, четвёрки и т.д. Что тогда можно сказать?

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

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 18:03 
В общем, если вы сообщите для каждой $n$-ки, пусто ее пересечение или нет, и вдобавок сообщите, какие из элементов покрытия ограничены, то можно будет, исходя из этого, посчитать гомологии одноточечной компактификации $\mathbb{R}^d$. С другой стороны, эта компактификация --- это $d$-мерная сфера, и ненулевые гомологии у нее лишь в 0 и в $d$, так вы и узнаете $d$. Как-то так.

Update. Поправил буквы --- непустоту пересечения надо знать для любого кортежа, и использованная там $n$ никакого отношения к размерности $d$ не имеет. Прошу прощения.

 
 
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 22:48 
Утундрий в сообщении #1015582 писал(а):
Narn
Вот зачем вы инцидентность на пересечение заменили, а?

А ведь и правда :oops: Вообще, если мы потребуем, чтобы все элементы покрытия $\{ F_i \}$ были выпуклыми замкнутыми множествами с непустой внутренностью, пересекающимися лишь по границе, и построим граф, в котором между $F_i$ и $F_j$ есть ребро тогда и только тогда, когда $F_i \cap F_j$ непусто (из графа, в котором между $F_i$ и $F_j$ нет ребра, если их пересечение состоит только из одной точки, мы нужной информации не извлечем), то этого достаточно, вроде бы. Ведь тогда можно смотреть на покрытие $\{A_i\}$, полученное очень малым раздутием $F_i$, и при этом $A_{i_1} \cap A_{i_2} \dots \cap A_{i_k}$ непусто в точности когда все $F_{i_1}, \dots, F_{i_k}$ друг с другом попарно пересекаются, то есть образуют клику в графе. Значит, весь нерв покрытия мы знаем из графа. Но без информации о том, какие элементы покрытия неограничены (или, для куба --- пересекаются с его границей), все равно не обойтись.

 
 
 
 Re: Вопрос про размерность
Сообщение16.05.2015, 22:54 
В предыдущем сообщении мною написана ерунда --- из графа для замкнутого покрытия нужной информации для открытого вытянуть нельзя.

 
 
 
 Re: Вопрос про размерность
Сообщение16.05.2015, 23:11 
Аватара пользователя
Narn, почему?

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

 
 
 
 Re: Вопрос про размерность
Сообщение17.05.2015, 00:06 
Вот к этому вранью очень легко привести контрпример:
Narn в сообщении #1015768 писал(а):
при этом $A_{i_1} \cap A_{i_2} \dots \cap A_{i_k}$ непусто в точности когда все $F_{i_1}, \dots, F_{i_k}$ друг с другом попарно пересекаются, то есть образуют клику в графе.

Почитать можно какой-нибудь учебник по алг. топологии. В статье википедии http://en.wikipedia.org/wiki/%C4%8Cech_cohomology
ссылка на Хэтчера, к примеру (стандартный учебник нынче, есть русский перевод, можно разжиться в сети). Есть еще хорошая книжка Edelsbrunner, Harer, Computational Topology. В сети доступен, насколько я знаю, ее черновой вариант. Она может показаться вам сильно проще.

Вообще, если вы можете выбирать постановку задачи (а я из вашего стартового поста понял, что у вас большая свобода в этом плане), то проще всего будет брать регулярные покрытия из маленьких множеств и делать по совету ИСН (это, в принципе, называется "размерность Хаусдорфа"). Общетопологическое определение размерности (в книге Александрова-Пасынкова) --- это, по-моему, чистейшая теория, с ее помощью эффективно считать, хоть на бумаге человеку, хоть на машине, очень сложно. Подход через гомологии требует, возможно, самых больших усилий на предварительную подготовку, но вполне реализуем, в том числе и в виде комп. программ (собственно, Эделсьбруннер-Харер про это).

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group