For the version of Wilson's ordering-counting problem where now we are interested, not in VERTICAL orderings, but rather in counting the number of DISTANCE orderings of our N points in D dimensions to an arbitrarily placed movable extra "red" point: UPPER BOUND: The number of cells of the arrangement of the H=(N-1)*N/2 bisecting hyperplanes for point-pairs. [Incidentally this arrangement is called the "all orders Voronoi diagram."] Incidentally, formulas counting cells for H-hyperlane arrangements in D-space have been worked out in the literature, I think by Zaslavsky. But since they obey recurrence that #cells(H,D) = #cells(H-1,D) + #cells(H-1,D-1). with base cases #cells(H,1) = H+1 and #cells(1,D) = 2 we can see that #cells(H,D) with H large D fixed is a polynomial in H of degree=D and lead coefficient 1/D!. LOWER BOUND: We can similarly to the notion of "k-sets" chopped off by hyperplanes, instead consider chopping using a sphere. Then the total number of sphere-cut k-sets (all k combined) is upper bounded by 2*(N choose D+1). Actually, if you map points in D-space onto the D-dimensional surface of a sphere in D+1 dimensional space via stereographic projection, then the hyperplane-cut k-sets on the higher diml set correspond to the sphere-cut k-sets on the lower diml set. I think the Clarkson-Shor proof still works even if points restricted to lie on a sphere. If so, then we get a lower bound for N large D fixed of form #distanceOrderings >= C_D * N^(D+1) / f(N) where f(N) grows to infinity arbitrarily slowly. So we are currently stuck in a quagmire on Wilson's ordering problems in which our upper bounds are roughly the square of our lower bounds. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)