A related question: Suppose I have two sets of n points in R^m, A and B. How hard is it to find the bijection A -> B that minimizes the sum of squared distances? For m=1 there’s a very efficient algorithm (your puzzle for the day), but for m>1 the best I know is solving the general minimum-weight bi-partite matching problem that grows as n^3 (for fixed m). The case where m grows with n might be interesting because a random set of points will often look quasi 1-dimensional when there are many axes to choose from. -Veit
On Mar 31, 2016, at 11:38 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Apologies for my lack of imagination, but I'm not understanding the problem. Except the part about ignoring cases where 2 or more distances are equal.
1) Are the points labeled?
2) Are you taking N labeled points, (selected in advance from whatever space and then asking what are their different orders from a variable additional point?
3) How are they selected?
((( The first 2 paragraphs seem to assume that in at least 1D, however they be selected there is going to be one answer, just a function of N. Possible, but not immediately clear to me.
But then in paragraphs 3 and 4, you are considering some probability distribution and mentioning a simulation, indicating that you agree that (in general) the answer is not necessarily just a function of N. )))
Keith, can you please express the problem rigorously so that the answers to my 3 questions above are included either explicitly or implicitly?
Many thanks,
Dan