Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

  eg
  -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 minimise 
   the expression ( provided they exist).

  -Just P= 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?

share|improve this question
    
@ARi, what do you mean by "integral point set"? –  Wlodzimierz Holsztynski Jun 19 '13 at 19:18
    
@ARi, thank you. –  Wlodzimierz Holsztynski Jun 21 '13 at 20:39
add comment

1 Answer

up vote 1 down vote accepted

This is not a direct answer, but rather an historical, and somewhat tangential comment. Way 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 30+ years, which you might trace via Google Scholar.

[Sax79] 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)

[Yem79] 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)


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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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