The discussion revolves around reconstructing a set of points M from a multiset D of pairwise distances. The proposed method involves sorting the distances and iteratively eliminating distances that can be expressed as the sum of two others, ultimately reducing the set to elementary distances. However, challenges arise in maintaining the correct order of these distances, as reflections and multiple configurations can yield the same distance set. Participants express skepticism about the effectiveness of the proposed method, suggesting the need for a more refined approach to select the appropriate distances. The conversation highlights the complexity of the problem and the potential for further exploration of algorithms that could simplify the reconstruction process.
#1
Vance
180
0
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 ?
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 !
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...
Last edited:
#4
Vance
180
0
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-
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:
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.
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:
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 !
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.)
