Meilleure façon de déterminer la dimension minimale d'une structure étant donné uniquement les distances entre les points

J'ai rencontré ce problème dans un domaine de la physique assez éloigné de l'informatique, mais cela semble être le type de question qui a été étudié en CS, alors j'ai pensé tenter ma chance en le posant ici.

Imaginez que l'on vous donne un ensemble de points et une liste de certaines des distances entre les points d i j . Quelle est la manière la plus efficace de déterminer la dimensionnalité minimale de l'espace dans lequel vous devez intégrer ces points? Autrement dit, quel est le plus petit k tel qu'il existe un ensemble de points dans R k satisfaisant aux contraintes de distances d i j . Je serais également satisfait d'une réponse pour C k , mais cela semble plus difficile.$\{v_i\}_{i=1}^n$$d_{ij}$$k$$\mathbb{R}^k$$d_{ij}$$\mathbb{C}^k$

Je suis heureux de dire que les distances doivent correspondre à uniquement avec une précision constante ϵ et que les points doivent être limités à des points sur un réseau d'espacement constant, afin d'éviter les problèmes de calcul avec des réels.$d_{ij}$$\epsilon$

En effet, je serais très satisfait d'une solution pour la version décisionnelle de ce problème, où étant donné et k on vous demande si un tel ensemble de sommets { v i } existe ou non. Trivialement, le problème est dans NP, car étant donné un ensemble de points dans R k, il est facile de vérifier qu'ils satisfont aux exigences de distance, mais il semble qu'il devrait y avoir des algorithmes de temps sous-exponentiels pour ce problème particulier.$d_{ij}$$k$$\{v_i\}$$\mathbb{R}^k$

L'approche la plus évidente semble être d'essayer de construire des structures dimensionnelles de manière itérative, en ajoutant des points supplémentaires un par un et en déterminant si une nouvelle dimension spatiale doit ou non être ajoutée à chaque itération. Le problème avec cela est qu'il semble que vous pouvez rencontrer des ambiguïtés où il existe plusieurs façons d'ajouter un point à la structure existante, et il n'est pas clair laquelle conduira à moins de dimensions lorsque vous continuerez à ajouter plus de points.$k$

Enfin, permettez-moi de dire que je sais qu'il est facile de créer des listes de distances qui ne peuvent être satisfaites dans un certain nombre de dimensions (c'est-à-dire celles qui violent l'inégalité du triangle). Cependant, pour les cas qui m'intéressent, il y aura toujours un nombre fini minimum de dimensions dans lesquelles un ensemble satisfaisant de points peut être trouvé.

Ce problème est parfois appelé l'achèvement de la matrice de distance euclidienne de faible dimension ou l'incorporation euclidienne de faible dimension d'un graphe pondéré.

Saxe [Sax79] et Yemini [Yem79] ont montré indépendamment par une simple réduction du problème de partition que ce problème est NP-complet même dans le cas d'une dimension; c'est-à-dire que le problème suivant est NP-complet pour k = 1:

Complétion de la matrice de distance euclidienne k- dimensionnelle / Incorporation euclidienne k- dimensionnelle d'un graphe pondéré
Instance : une matrice symétrique M dont les entrées sont soit des entiers positifs en binaire soit «inconnus».
Question : Les entrées inconnues dans M peuvent-elles être remplies par des nombres réels afin que M devienne une matrice de distance de points dans l'espace euclidien k- dimensionnel ℝ ^k ?
De manière équivalente,
Instance : Un graphe G où chaque bord a un poids entier positif écrit en binaire.
Question : Les sommets de G placés dans lek -Espace euclidien dimensionnel ℝ ^{k de} sorte que pour chaque bord de G , la distance entre les deux extrémités soit égale au poids du bord?

De plus, Saxe [Sax79] a montré (par une réduction plus impliquée de 3SAT) que l' achèvement de la matrice de distance euclidienne de dimension k reste NP-difficile même sous la restriction que toutes les entrées connues dans M sont soit 1 ou 2, pour chaque constante entière positive k . En particulier, le problème est NP-complet même lorsque les entrées connues dans M sont données en unaire. [Sax79] contient également des résultats de dureté sur l'intégration approximative.

Soit dit en passant, je ne pense pas qu'il soit trivial que le problème se trouve dans NP; notez que vous avez besoin de coordonnées irrationnelles dans certains cas lorsque k > 1. Je ne sais pas s'il est connu pour être dans NP.

Les références

[Sax79] James B. Saxe. L'intégration des graphiques pondérés dans l' espace k est fortement difficile à NP. In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing , pp. 480–489, 1979. Aussi dans James B. Saxe: Two Papers on Graph Embedding Problems , Department of Computer Science, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini. Quelques aspects théoriques des problèmes de position-localisation. In 20th Annual Symposium on Foundations of Computer Science (FOCS) , pp. 1-8, oct. 1979. DOI: 10.1109 / SFCS.1979.39

$d$$n$$d$$n$