Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier 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?

 A: 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).)
