From D to M, how far and what way

[Vance]

Let's call M a set of points on the line and D the multiset of all pairwise distances between points in M.

In case you were given D, would you be able to find M ? In what way ?

 

[Gokul43201]

Preliminary answer : Sort the set $$M = {d_i~|~i = 1..\frac {n(n-1)}{2}}$$

where n is the cardinality of set D, or the number of points.

Start with the largest $$d_i$$ in M and cross it out if $$d_i = d_j + d_k, ~~d_j,d_k ~~\epsilon ~M$$

Repeat this process till the set is reduced to a set of elementary distances, M' whose cardinality is n-1. Stop here.

Hmmm...clearly there's more that needs to be done to identify the correct order among these elementary distances that involved the larger distances. I've lost info along the way...but I've got to go now...so perhaps, later !

 

[Gokul43201]

Preliminary answer : Sort the set $$M = {d_i~|~i = 1..\frac {n(n-1)}{2} }$$

where n is the cardinality of set D, or the number of points.

Start with the largest $$d_i$$ in M and cross it out if $$d_i = d_j + d_k, ~~ d_j,d_k ~~\epsilon ~~M$$

Repeat this process till the set is reduced to a set of elementary distances, M' whose cardinality is n-1. Stop here.

Hmmm...clearly there's more that needs to be done to identify the correct order among these elementary distances that involved the larger distances. I've lost info along the way...but I've got to go now...so perhaps, later !

Okay, when you find $$d_i = d_j + d_k$$, you do 2 things :

1) Eliminate d(i)

2) Find max{d(j),d(k)} = d(k), say - actually you are just picking anyone of the two elements here. Change the position of d(k) in the remaining set, so that it's now a neighbor of d(j) but has not come in between another such pair involving d(j). This is always possible - no proof provided !

Continue as above...

 

[Vance]

How can you do that so soon ?
It took me so much time ...--lol--

Well, wake up in the morning and the first thing to do is check PF ? -lol-

 

[NateTG]

Let's call M a set of points on the line and D the multiset of all pairwise distances between points in M.

In case you were given D, would you be able to find M ?

Since you can't eliminate reflections using any of the information, the answer is no.

Consider, for example, that three points with gaps of 2 and then 1, and three points with gaps of 1 and then 2 will both produce distances of 1,2 and 3.

Gokul:

I'm fairily certain that there is a process that generates all of the 'prime gaps' for lack of a better expression, but I'm not convinced that your process works:

Consider the set of points with the inital gaps (in order) as:
3 1 3 2 3 4 3
Which generates the following 21 distances:

3 4 7 9 12 16 19
  1 4 6  9 13 16
    3 5  8 12 15
      2  5  9 12
         3  7 10
            4  7
               3

Now, sorting them yields:
{1,2,3,3,3,3,4,4,4,5,5,6,7,7,7,8...19}
If we apply your process, as far as I can tell, you end up with a multiset that doesn't contain 4 as the set of primitive distances.

You may be able to improve the process by specifying which $$d_j,d_k$$ to use.

 

[Vance]

Thanks again,

 

[Gokul43201]

Since you can't eliminate reflections using any of the information, the answer is no.

Consider, for example, that three points with gaps of 2 and then 1, and three points with gaps of 1 and then 2 will both produce distances of 1,2 and 3.

Gokul:

I'm fairily certain that there is a process that generates all of the 'prime gaps' for lack of a better expression, but I'm not convinced that your process works:

Consider the set of points with the inital gaps (in order) as:
3 1 3 2 3 4 3
Which generates the following 21 distances:

3 4 7 9 12 16 19
  1 4 6  9 13 16
    3 5  8 12 15
      2  5  9 12
         3  7 10
            4  7
               3

Now, sorting them yields:
{1,2,3,3,3,3,4,4,4,5,5,6,7,7,7,8...19}
If we apply your process, as far as I can tell, you end up with a multiset that doesn't contain 4 as the set of primitive distances.

You may be able to improve the process by specifying which $$d_j,d_k$$ to use.

Yes, I think the trick might be to find the right d_j, d_k...but I can't seem to figure out how to choose. Perhaps, the nearest ones to d_i/2 ?

Now, I'm starting to think this is not possible...even allowing for choice of origin and reflections.

PS : I rescind that previous line...sounds like this is worth thinking about further !

PPS : There are solutions whose sizes go like n! - but surely you are looking for non-NP complete algorithms !

 

[NateTG]

Yes, I think the trick might be to find the right d_j, d_k...but I can't seem to figure out how to choose. Perhaps, the nearest ones to d_i/2 ?

Now, I'm starting to think this is not possible...even allowing for choice of origin and reflections.

PS : I rescind that previous line...sounds like this is worth thinking about further !

PPS : There are solutions whose sizes go like n! - but surely you are looking for non-NP complete algorithms !

Well, the example I gave was designed to be difficult to deal with. I don't think that the algoritms have to be NP hard either. It seems like there should be some way to fill out a triangle like the onle I have in my previous post, since every number in the triangle must be smaller than all numbers above and to the right of it (and there are a bunch of other relationships that can be used.)