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

[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$ вам придётся рассмотреть почти все пары точек. Это не строго, но диаграмма состоит из симплексов. А вам надо посмотреть все симплексы чтобы получить систему с одним решением.

[B@R5uk]

slavav, спасибо за комментарий! Можете привести, пожалуйста, ссылку, где обсуждается приведённая вами вычислительная сложность триангуляции Делоне (для общего развития)? Всё, что мне удалось по-быстрому нагуглить, — это формула $O(n\log n)$ в вики для метода "разделяй и властвуй" в случае плоскости и разные невразумительные упоминания для случая 3D там и сям.

Тем не менее, мне кажется, что триангуляция Делоне является здесь плохим примером для сравнения (если я не прав, поправьте меня). Главный аргумент, алгоритм триангуляции — это оптимизационный алгоритм. Он должен сделать информированный выбор единственного (с оговоркой) набора рёбер (соответствующего критерию Делоне) из всех допустимых наборов Ω. Для того, чтобы получить информацию для этого выбора он должен сделать как минимум

$$K_{comp}=\log_2|\Omega|$$

сравнений каких-то величин. Очень грубо число допустимых наборов можно оценить сверху как 2 в степени число возможных рёбер (каждое ребро либо есть, либо отсутсвует), которое считается через число точек N:

$$|\Omega|\ll|\Omega_{full}|=2^{\frac{N(N-1)}{2}}$$

Этот выбор сильно отличается по своей природе от того, какое решение требуется принять в моём вопросе выше (эквивалентность двух множеств точек). А ещё, триангуляция Дэлоне из двух возможных рёбер не всегда выбирает кратчайшее.

Вообще, я тут понял, что немного натупил с последним вопросом. Множества точек, что я рассматриваю, являются локально-оптимальными решениями обобщённой задачи Таммеса в заданном пространстве. Множество рёбер с минимальной длиной (равной точной нижней границе на длину ребра) образуют так называемый граф соприкосновений/граф соседства (contact graph). Во всех статьях, что мне попадались, люди ведут себя так, как будто знание этого графа достаточно, чтобы однозначно восстановить положение точек (с точностью до вращения, трансляции и прочих симметрий), даже нижняя граница на длину между точками не нужна. Я, правда, нигде на формальное доказательство этого факта не натыкался почему-то. Однако, нахождение взаимного расположения точек по скудной информации, содержащейся в этом графе является трудоёмкой оптимизационной задачей. И я хочу избежать этой трудоёмкости.

Я так же понял тут, что мне на самом деле нужно две задачи решить. Первая: по двум вышеописанным последовательностям троек определить, являются ли два множества точек одинаковыми (с точностью до симметрий) или разными. При этом хотелось бы (во-первых) использовать самый простой алгоритм, а именно: последовательное сравнение пар длин рёбер, взятых одна за другой из двух последовательностей. Если при таком алгоритме, мы натыкаемся на пару длин не равную друг другу, то мы сразу можем быть уверенными, что эти два множества точек разные. Разумеется, для большинства решений задачи Таммеса различие наступит уже в первом же взятом ребре (то есть они будут отличаться своей точной нижней границей на длину рёбер). Однако, имеются примеры, в том числе глобально оптимальных решений, когда изменение положения одной или нескольких точек не приводит к изменению положения всех остальных точек (наглядный пример для плоского 2-тора постараюсь приготовить и привести позже). Чтобы отличить такие два решения потребуется прочитать довольно много элементов последовательности троек. При этом хотелось бы (во-вторых), хранить не всю последовательность (квадратичную по числу вершин N), а лишь её начальную часть (линейную по N). Для этого необходимо быть уверенным, что ожидаемое ребро, дифференцирующее эти два множества как разные, действительно встретится в этой обрезанной последовательности. Поэтому вопрос: можно ли оценить индекс (в последовательности троек) этого дифференцирующего ребра сверху линейной по N оценкой? И если да, то с каким коэффициентом?

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

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

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

$$K_{comp}=\log_2\lBig(N!\rBig)\approx N\log_2N$$

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

Что-то меня разнесло мыслию по древу. Надеюсь, кто-нибудь что-нибудь разумное посоветует. Особенно в вопросе: можно ли подойти к проблеме эквивалентности двух множеств точек (с учётом изометрий пространства) более рационально?

[slavav]

https://en.wikipedia.org/wiki/Delaunay_ ... el1995_4-0

Для каждой точки триангуляция Делоне содержит ребро до ближайшей другой точки множества. То есть, в ней довольно много рёбер которые будут выданы вашему алгоритму. Это утверждение не является строгим. Я только указал возможную связь.

[B@R5uk]

B@R5uk в сообщении #1691113 писал(а):

наглядный пример для плоского 2-тора постараюсь приготовить и привести позже

Пример:

Координаты точек в примере:

Используется синтаксис Matlab M

num_short_1 = 20;
coords_1 = [
    0.780292834470301   0.202217589393753
    0.636945602651561   0.928326384090630
    0.219707165529698   0.797782410606247
    0.910836807954685   0.784979152271891
    0.363054397348438   0.071673615909370
    0.232510423864054   0.488912053031233
    0.089163192045315   0.215020847728110
    0.767489576135945   0.511087946968767
    0.506401629167178   0.345564821212493
    0.493598370832822   0.654435178787507
]';
num_short_2 = 20;
coords_2 = [
    0.764677785454991   0.205715504620943
    0.621330553636252   0.931824299317819
    0.204092116514389   0.801280325833436
    0.895221758939375   0.788477067499080
    0.347439348333128   0.075171531136559
    0.216895374848745   0.492409968258422
    0.073548143030005   0.218518762955299
    0.908025017273731   0.479606709924066
    0.490786580151868   0.349062736439682
    0.477983321817512   0.657933094014696
]';
num_short_3 = 18;
coords_3 = [
    0.767238437121863   0.180543973484383
    0.623891205303123   0.906652768181260
    0.206652768181260   0.776108794696877
    0.932761562878138   0.919456026515617
    0.350000000000000   0.050000000000000
    0.219456026515616   0.467238437121863
    0.076108794696877   0.193347231818740
    0.850000000000000   0.550000000000000
    0.493347231818740   0.323891205303123
    0.480543973484384   0.632761562878137
]';
num_short_4 = 20;
coords_4 = [
   0.749062736439682   0.209213419848132
   0.605715504620943   0.935322214545008
   0.188477067499080   0.804778241060625
   0.879606709924066   0.791974982726269
   0.331824299317819   0.078669446363748
   0.201280325833436   0.495907883485611
   0.057933094014696   0.222016678182488
   0.892409968258422   0.483104625151255
   0.475171531136559   0.352560651666871
   0.618518762955299   0.626451856969994
]';
 

B@R5uk в сообщении #1691113 писал(а):

Поэтому вопрос: можно ли оценить индекс (в последовательности троек) этого дифференцирующего ребра сверху линейной по N оценкой?

Скорее всего нельзя. Контр-пример должен иметь такое, довольно правдоподобное свойство: после перемещения одной точки, все расстояния от этой точки в новом её положении до остальных точек образуют точно такой же отсортированный список, как и список в предыдущем её положении, за исключением каких-нибудь самых последних (в нём) расстояний.

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