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

13

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.{vi}i=1ndijkRkdijCk

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.dijϵ

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.dijk{vi}Rk

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é.

Joe Fitzsimons
la source
1
Je suppose que vous voulez une intégration dans ? 2
Suresh Venkat
@Suresh: Oui, désolé, je voulais ajouter ça.
Joe Fitzsimons
1
Quel est le domaine de la physique d'où cela vient, au fait?
Vinayak Pathak,
@Vinayak: Je viens de le rencontrer en essayant de calculer quelque chose en mécanique quantique.
Joe Fitzsimons,

Réponses:

13

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

Tsuyoshi Ito
la source
1
Merci. Certes, dans le cas général, ce n'est pas évidemment dans NP, mais si vous le transformez en un problème de promesse en limitant les points à allonger sur un réseau, et à la place, on donne le carré des distances, plutôt que les distances elles-mêmes, alors toutes les distances carrées sont des entiers, et donc une solution peut être vérifiée exactement en temps polynomial.
Joe Fitzsimons
11

dndn

Suresh Venkat
la source
1
Génial, cela pourrait être juste le pointeur dont j'avais besoin. Désolé de perdre votre temps si c'est une question quelque peu banale.
Joe Fitzsimons,
1
Ce n'est pas anodin si vous ne vous moquez pas de la géométrie des distances :)
Suresh Venkat
J'ai lu votre message, et il semble certainement me diriger dans la bonne direction. Cependant, je ne suis pas tout à fait clair comment cela s'appliquerait avec seulement un ensemble partiel de distances. Pourriez-vous m'éclairer?
Joe Fitzsimons,
Ah, le problème que je réalise, c'est qu'il ne gère pas le cas partiel. :(
Suresh Venkat
1
@Joe: Une matrice de distance satisfait toutes les inégalités de type négatif si et seulement si la «matrice de Gram» correspondante est semi-définie positive. (Je mets «Gram matrix» entre guillemets effrayants car ce n'est pas vraiment une matrice Gram à moins que la distance ne soit réalisable dans un espace euclidien.) Cependant, je ne sais pas comment gérer la restriction de dimension en utilisant cette approche.
Tsuyoshi Ito