Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.

Q1. What is the least time complexity possible/known for recreating the Integral point set $P$ given $D$ through a Turing machine computable algorithm?

Q2. What is the shortest string which can describe $P$?

For example:

  • Using $D$ to describe $P$ may be a shorter method than $P$ itself;

  • Scaling $D$ down to elements all relatively prime may still shorten the description string.

  • Using a certain set of computed values to describe $P$ may further minimize the expression ( provided they exist).

  • Just $P= \text{IntegralPointSet}(n)$ will be problematic as

    • It is not Turing computable. (Comments?)
    • It does not define exactly the point set we want out of possibly many such integral point sets.

Which gets me to the third question:

Q3. What is the shortest string required to uniquely identify a particular integral point set of cardinality $n$ amongst all other such integral point sets?


This is not a direct answer, but rather an historical, and somewhat tangential comment. Back in 1979, the general problem you posed was proved NP-hard by Saxe and by Yemini independently. There has been quite a rich literature on this topic in the last 35+ years, which you might trace via Google Scholar. Added. For example, see the 2014 survey below.

James B. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979. Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980. (PDF download.)

Yechiam Yemini. Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979. DOI: 10.1109/SFCS.1979.39 (ACM link.)

Liberti, Leo, Carlile Lavor, Nelson Maculan, and Antonio Mucherino. "Euclidean distance geometry and applications." Siam Review 56(1) (2014): 3-69. (Journal link.)

           (Figure from "Untangling planar graphs from a specified vertex position—Hard cases" (Elsevier link).)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.