Sign up ×
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$?

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?

share|cite|improve this question

1 Answer 1

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)

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

share|cite|improve this answer

Your Answer


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.