On 10/18/14, Warren D Smith <warren.wds@gmail.com> wrote:
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 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)).
--there is a problem which probably requires me to retract my claim to have "overcome quagmire." Edelsbrunner in his theorem 13.30 claims to construct all Kth order VoD's for each K=1,2,3,... in time and space O(N^(D+1)). (VoD=Voronoi diagram.) However this is not the same thing as constructing the "all-order VoD," which is sort of the union of all the Kth order VoDs. I had been acting as though it were the same thing. If it were, then I believe I now can prove matching upper & lower bounds of order N^D for Wilson's vertical ordering problem. But it probably isn't. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)