Координаты точек по матрице расстояний

[квит]

Прямая задача.
Дан набор точек, заданных своими координатами (xi,yi).
По ним можно рассчитать матрицу попарных расстояний между точками
dij=sqrt( (xi-xj)^2+(yi-yj)^2 )

Обратная задача.
Дана матрица расстояний между точками D=(dij). Т.е. dij - расстояние между двумя точками (xi,yi) и (xj,yj)
Можно ли найти координаты точек?

[BOBA]

Иногда, многогранник жёсткий. тогда, с точностью до поворотов и переносов, наверное.

[BOBA]

Если мы на плоскости то жёсткий это треугольник. Если в объеме то тетраэдр.

[квит]

Сообщение от BOBA

Иногда, многогранник жёсткий. тогда, с точностью до поворотов и переносов, наверное.

если три точки, то да, треугольник

если точек больше, то уже не вариант)))

[BOBA]

То есть по матрице надо понять, все ли жёсткие фигуры жёстко связаны между собой прямо или косвенно.

[квит]

Сообщение от BOBA

То есть по матрице надо понять, все ли жёсткие фигуры жёстко связаны между собой прямо или косвенно.

ну и вообще - можно ли при заданной матрице найти такую систему точек на плоскости

матрица расстояний - частный случай, более общее понятие - матрица различий, чем показатель меньше, тем менее различаются объекты, и наоборот

может иметь в принципе любой смысл

1. например, расстояние по графу дорог
тогда, если две точки на карте расположены напротив друг друга через железную дорогу (или речку), а переезд через 10 км - в евклидовом пространстве должны быть разнесены друг от друга далеко

2. время проезда от точки А в точку Б. Если есть временные окна - тогда время проезда + время ожидания, если приехали раньше назначенного времени

3. стоимость проезда - если например, развозим не груз. а мастер по заявкам выполняет настройку оборудования - тогда стоимость проезда + стоимость работ

4. сложность выполнения заявки - может быть вообще в баллах (или усл. ед.)

[квит]

Сообщение от квит

более общее понятие - матрица различий

в такой постановке могут возникать разные сложности

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

2. матрица различий не обязана быть симметричной (dij=dji), например, в случае односторонней дороги, из А в Б едем 5 мин, а обратно - 15 мин

3. граф может быть неполным, первый клиент ждет товар с утра, второй вечером, тогда от А до Б есть путь, обратно нет

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

и еще куча всяких нюансов и заморочек.... )))

[Afa]

Сообщение от квит

Прямая задача.
Дан набор точек, заданных своими координатами (xi,yi).
По ним можно рассчитать матрицу попарных расстояний между точками
dij=sqrt( (xi-xj)^2+(yi-yj)^2 )

Обратная задача.
Дана матрица расстояний между точками D=(dij). Т.е. dij - расстояние между двумя точками (xi,yi) и (xj,yj)
Можно ли найти координаты точек?

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

[BOBA]

Ну, если граф предполагается на эвклидовых точках, то можно поставить вопрос о его жёсткости.

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

Третий признак равенства треугольников по 3 сторонам.

А вот четырехугольник по четырем сторонам равнять нельзя у них углы варьировать можно. Но задав доп ограничения опять можно жёстким сделать.

Поэтому вопрос о жёсткости графа не лишён какого то топологического смысла.

[BOBA]

Допустим граф построен по ограничениям расстояний. Если существует такое расстояние эль малое, что переместив любую вершину кроме нулевой на это или меньшее расстояние, можно путем смещения остальных вершин сохранить весь набор ограничений, то граф нежесткий.

Так себе определение, конечно....