Dan Asimov <dasimov@earthlink.net> wrote:

1) Are the points labeled?

Yes, if only by their coordinates. I didn't mention this, since the solution obviously doesn't depend on what they're labeled or in what order they're labeled. I thought it went without saying that they're not to be renamed in the middle of the solution, just as I didn't mention in my dead president's puzzle that it's not okay to get additional sort orders by renaming Wilson "Jefferson" and vice versa.

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?

Yes.

3) How are they selected?

Randomly, with uniform probability distribution within some range, and no points outside it. As I mentioned, in the 2D infinite plane case, that range is the interior of a circle, but I'm not sure that makes any difference. In the 2D sphere, torus, and Klein bottle cases, that range is the whole 2D surface. The location of the variable additional point is not constrained, except that it's within the space. And, to avoid zero-measure pathologies, it can't be equidistant from three of the labeled points. (Other zero-measure pathologies to be avoided are equidistant labeled points, three labeled points on the same line (except in the 1D case), four labeled points in the same plane (except in the 2D case), etc., two of the labeled points being in the same place, and two of the lines connecting pairs of labeled points being parallel (except in the 1D case). There may be others.)

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.

Yes, which is why I didn't bother to give a distribution for them. It doesn't matter how they're distributed, so long as no two are in the same place and no two of their N-choose-2 pairwise distances are equal. As I mentioned, the solution is the same as for the dead presidents problem, which makes me wonder if they're the same problem in disguise.

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.

I don't have any intuition as to whether there's a unique solution for 2D, or whether it depends on the arrangement. I have determined that if the "variable additional point" is constrained to be very distant from the circle containing all the labeled points, that the first point in the sort order will always be one of the labeled points in the convex hull of the labeled points, and that the number of the points in the convex hull, if N>2, can be anything from 3 to N. But that's very weak evidence about the more general case.

Keith, can you please express the problem rigorously so that the answers to my 3 questions above are included either explicitly or implicitly?

I hope I have done so now. It's not easy being totally unambiguous. Especially when dealing with something random. It's even worse than the problem of proofreading my own text. *I* know what I meant, so it's easy to read what I meant rather than what I wrote. (And I have worked as a professional proofreader.)