We anyhow remain stuck in a quagmire on Wilson's ordering problems in which our upper bounds are roughly the square of our lower bounds.
--Quagmire now overcome. I looked in H.Edelsbrunenr: Algorithms in combinatorial geometyr, Springer 1987. In chapter 2, he also invents "Wilson's" ordering problem, but only in 2 dimensions, under the name "circular sequences", and shows, basically, lower and upper bounds of form N^2 +- O(N), and also shows that when N<=4 all N! orderings are possible but when N=5 fewer then N! are possible. In section 13.3 he discuses "higher order voronoi diagrams"... as I said in earlier posts, the number of cells in the all-orders VoD of the N points in D-space, is the number of distance-orderings. Well, Edelsbrunner (theorem 13.30) shows how to compute the all-order-VoD by computing an arrangement of N hyperplanes in D+1 dimensional space... which he accomplishes in time and space both O(N^(D+1)). The number of distance orderings is thus O(N^(D+1)) for N large D fixed. This upper bound happens to almost match my lower bound of order N^D / f(N). The "squaring quagmire" is thus overcome, and we are closing in on the truth, which is probably N^(D+1). Wilson's vertical ordering problem is the special case of his distance-ordering problem when we demand the "red point" must lie on the sphere at infinity. In other words, we now have to count the number of all-order-VoD cells where only the infinite-volume cells are counted. This yields by Edelsbrunner's same arrangement trick, an upper bound now of order N^D. Edelsbrunner section 13.4 also finds the exact complexity of k-order VoD in the plane (D=2). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)