Пространственно-размерное

[spamsink]

Вопрос к математикам и к примкнувшим к ним.

Допустим, у нас есть некоторый набор абстрактных точек, и нам известны попарные расстояния между этими точками, приведенные с точностью N значащих цифр.

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

Comments

[juan_gandhi]

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

[smugastyi_kit]

Прямо как у нас, в демо-мейкинге, marching-cubes alghoritm.

Порядок присобачивания важен?

[malobukov]

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

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

Re: Порядок присобачивания важен?

[juan_gandhi]

Я бы не гарантировал.

[spamsink]

А если евклидовость не обещали?

[juan_gandhi]

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

[spamsink]

Вот что мне порекомендовали

[juan_gandhi]

Отличный линк; спасибо!

[codedot]

С кривизной пространства, можно и в три измерения уложить.

[spamsink]

И какая будет метрика, чтобы уложить в три измерения 4 точки с попарными расстояниями, равными 1?

[codedot]

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

P. S. Строго говоря, три измерения нужны, только если требуется локальная евклидовость. Без этого условия и двух измерений достаточно: одна двусторонняя плоскость с via вполне подойдет. Вполне возможно, мы все на печатной плате живем :)

[spamsink]

Насчет четырех точек это мне уже было спать пора. 4-мерная сфера - это хорошо.

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

Вполне возможно, мы все на печатной плате живем

Я вольфрамову книжку не читал, поэтому не знаю, придумал он уже клеточные автоматы на двусторонней плоскости с via, или нет.

[codedot]

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

[spamsink]

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

[codedot]

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

В общем, в задаче следует уточнить, о каком именно пространстве идет речь.

[spamsink]

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

Впрочем, тогда я лишаюсь возможности оптимально определять размерность пространства с "почтово-железнодорожной" метрикой. Чёрт.

[codedot]

Я вам больше скажу. Такое универсальное пространство может быть еще и счетным.

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

[spamsink]

Можно им ограничиться, как juan_gandhi предлагает, но ведь Not every finite metric space can be isometrically embedded in a Euclidean space, поэтому в худшем случае придется прибегнуть как минимум к неевклидовой метрике в Rⁿ, определенной на попарных разностях координат.

Буду читать Open problems on embeddings of finite metric spaces.