Как много расстояний нужно?

[B@R5uk]

В пространстве конечной размерности D имеется множество точек, количество которых N больше размерности пространства (оба числа известны). Требуется определить их взаимное расположение. Координаты точек не известны, но известны расстояния между ними. Однако, эти расстояния можно получать только поочерёдно, в порядке возрастания их величины, начиная с самого короткого. То есть расстояния между точками заданы в виде конечной последовательности троек: два индекса для двух точек и расстояние между этой парой. Вопрос: как много элементов последовательности необходимо просмотреть, чтобы однозначно определить взаимное расположение точек?

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

Как действовать в общем случае, я что-то ума не приложу. В идеале хотелось бы обойтись количеством расстояний порядка DN, но меня берут сомнения, что так можно будет сделать всегда.

[dgwuqtj]

Если у вас все точки, кроме одной, лежат в единичном шаре, а оставшаяся где-то далеко, то придётся посмотреть хотя бы $\frac {(N - 1) (N - 2)} 2 + D$ расстояний.

[B@R5uk]

dgwuqtj, спасибо за контр-пример! То есть, результат сильно зависит от взаимного расположения точек, и для произвольного расположения в худшем случае может потребоваться прочитать почти всю последовательность троек.

А что, если на расстояния l между точками наложены ограничения? Что-то в духе

$$c_1\sqrt[D]{N}\le l_{ij}\le c_2\sqrt[D]{N}$$

Вообще, опять же, у меня пространства компактные: D-сфера

$$\mathbb{S}^D=\left\{||x||=1,\;x\in\mathbb{R}^{D+1}\right\}$$

или D-тор $\mathbb{T}^D=[0,\;1]^D$, и точки заполняют их в некотором смысле равномерно, во всяком случае нижняя и верхняя границы на расстояния между ними присутствуют.

Я так понимаю, для каждой точки из последовательности троек нужно извлечь как минимум D расстояний до любой другой точки (если забыть на время, про то, что точки могут лежать на одной прямой, в одной плоскости и так далее). Как только последнее такое расстояние извлечено, то взаимное расположение точек определяется однозначно. Тут у меня, правда, загвоздка: для каждой точки по крайней мере D+1 (возможно больше) наименьших расстояний все равны между собой и, соответственно, равны нижней границе. Поэтому гарантированно потребуется больше, чем (D+1)N извлечений из последовательности. Я поэтому задумался: можно ли обойтись удвоенной или утроенной величиной? Или я что-нибудь путаю?

[slavav]

Кратчайшие расстояния между парами точек связаны с триангуляцией Делоне, которая может иметь сложность $O(N^{\left\lceil\frac{D}{2}\right\rceil})$. То есть уже $D \geqslant 3$ вам придётся рассмотреть почти все пары точек. Это не строго, но диаграмма состоит из симплексов. А вам надо посмотреть все симплексы чтобы получить систему с одним решением.