[math-fun] counting orderings of points in D-space
To generalize Wilson's problem to D-space, combining previously posted ideas, if there are N points inside a D-dimensional ball, N large, D fixed, then the number of possible orderings of the N points along the X-coordinate (when the ball is rotated) is upper bounded by: if D=1: 2. if D=2: N*(N-1). if D>2: Any point-pair defines a "great-circle" (hyperplane intersect sphere) from bisector hyperplane. The arrangement defined on the sphere-surface by these H=N*(N-1)/2 hyperplanes has F faces, and the generic value of F upper bounds the number of orderings. And obviously F(H,D) is upper bounded by F(H,D) <= F(H-1,D-1) + F(H-1,D) which allows us to compute a table of upper bounds starting from F(H,2) = 2*H and F(1,D) = 2. (This is, of course, the Pascal triangle recurrence...) Note that F(H,D) with H large and D fixed is bounded by a degree=(D-1) polynomial in H, you can prove this inductively. Its leading (highest degree) term should have coefficient=4/D! when D>1.
Re the number of orderings of N points in D-space, in my previous post I showed it was upper bounded by a polynomial in H of degree D-1 and leading coefficient <= 4/D!, where H=N*(N-1)/2. I now produce a lower bound. The new insight is to think about (what have been called in the literature) "k-sets." http://en.wikipedia.org/wiki/K-set_(geometry) A k-set is a k-element subset (or for some other authors, a <=k-element subset) of N points got by chopping a fixed N-point set with a hyperplane, the k-set is what is on one side. Not all 2^N subsets are achievable. The total number of k-sets of a generic N-point set in D-space (for all k combined) is at most 2*(N choose D) because you can move the separating hyperplane until it is about to touch D of the N points, all on one side; this leaves the subset unaffected. This upper bound is, in fact, tight up to (at most) a dimension-dependent multiplicative constant factor. THat was shown by K.L. Clarkson & P.W.Shor: Applications of random sampling, II, Discrete Comput. Geom. 4,1 (1989) 387-421. http://www.cs.duke.edu/courses/spring07/cps296.2/papers/clarkson-shor.pdf Also perhaps of interest: the number of "halving hyperplanes" (k-sets with k=N/2, essentially) is known to be lower bounded by BigOmega( N^(D-1) * logN ) due to L.Lovasz and/or E.Straus in 1971 when D=2, and R.Seidel for D>2. L.Lovasz: On the number of halving lines, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 14 (1971) 107-108 there also are interesting upper bounds on halvings... Now obviously the number of k-sets is upper bounded by the number of orderings (Wilson's problem) times N/2. Hence Theorem: The number of Wilson-orderings of N generic points in D-space is lower bounded by BigOmega( (4/N) * (N choose D) ) for N large, D fixed. There is a substantial gap between the upper and lower bounds... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Clarkson & SHor
--I must correct an error -- Clarkson & Shor's bounds on the number of k-sets (all k combined) were not quite as strong as I'd said. Their lower bound (and my easy upper) are C_D * N^D / f(N) <= #sets <= 2 * (N choose D) where f(N) has to go to infinity with N, arbitrarily slowly... for example loglogloglogN... this valid when N large, D fixed, any fixed epsilon>0. Thus these bounds do not quite match. [But one can match the upper bound when D<=2.] Hence my lower bound on #WilsonOrderings has to be slightly reduced from what I'd said, by a factor f(N). Since for every ordering, we get a halving (namely the set that is the first half of the ordering), we also find from the Lovasz-Seidel lower bound on halvings a different lower bound #Orderings >= N^(D-1) * logN * C_D for N large, D>=2 fixed. This is not as good as my lower bound using Clarkson-Shor as corrected.
There is a substantial gap between the upper and lower bounds...
It now occurs to me how to find a different upper bound for Wilson's ordering problem. For simplicity focus on the case D=3 dimensions, N generic points. Suppose they have some "vertical" ordering. Rotate the point set bodily by the least possible angle needed to change the vertical ordering, minus epsilon. This causes exactly two of the points, A & B, to have almost-equal heights (rotating a bit more would swap them in the order). Now fix the line thru AB, and rotate the point set bodily about said line, by the least possible angle to change the ordering, minus epsilon. Now, we either have exactly 3 points A,B,C at almost same height, or we have two pairs of points A,B and A',B', with both pair members at almost-same height. (Throughout we agree to regard epsilon as infinitesimally small positive.) The point set now is frozen and cannot be rotated further. So in this way, each ordering is associated via a 1-to-1 or 1-to-many map, to either an ordered triple of points A,B,C, or two ordered pairs of points A,B and A',B'. Hence when D=3 the number of orderings is upper bounded by N*(N-1)*(N-2)*(N-3) + N*(N-1)*(N-2) = N*(N-1)*(N-2)^2. Now stop fixing D=3 and allow any dimension. The initial rotation finds two points A & B which then become of almost same height. But now, since we fix the line AB and rotate while preserving line, we have a D-1 dimensional problem. This allows an induction on #dimensions. Thus we find: #orderings(D,N) <= N*(N-1) * #orderings(D-1,N-2). This does not seem as good as my previous upper bound in large dimensions, but might be of some use. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
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)
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.
--arggh, sorry, I forgot to multiply by 2/N. So it really would yield #distanceOrderings >= C_D * N^D / f(N) where f(N) grows to infinity arbitrarily slowly. 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.
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)
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)
The "circumcenter" of a triangle, is the intersection of the perpendicular bisectors of its 3 sides. More generally the circumcenter of a D-dimensional simplex is the unique intersection of the perpendicular bisectors of its (D+1)D/2 sides. This is relevant since, as J.P.Grossman pointed out when D=2, the arrangement of H hyperplanes that are bisectors of point-pairs [N points in D dimensions, H=(N-1)N/2] -- also known as the "all orders Voronoi diagram" -- is not a generic set of H hyperplanes. It features those concurrences of (D+1)D/2 hyperplanes, which is way more than the concurrences of only D hyperplanes that are the most that ever happen for a generic hyperplane set. Furthermore we have for example when D=3, often 3 hyperplanes are concurring on a common line. Grossman then asserted (without any proof) when D=2 these were the only ways in which the hyperplane (i.e. line) set is nongeneric. What is the basis of this assertion? Anyhow, in the event we can prove the D-dimensional version of this, then probably we can do the combinatorics for this kind of hyperplane arrangement to find exact answer for counting distance-orderings of N points in D-space. The "lifted" 1-higher dimensional arrangement described by Edelsbrunner (another way of viewing this problem) is probably very useful for understanding this. Specifically, for each of the N points x=(x1,x2,...,xD) in D-space, define an (D+1)st new coordinate z = x1^2 + x2^2 + ... + xD^2. This is a paraboloid P. Now consider the N hyperplanes that are tangent to P at our N points. These N hyperplanes define an arrangement A in (D+1)-space. The vertical projection of A down into D-space (i.e. take z->0) is the all-orders Voronoi diagram. Its upper surface corresponds to the ordinary Voronoi diagram. Etc etc. These N hyperplanes are (compared to the H hyperplanes) "more generic." Namely each is defined by D real numbers, as opposed to the D+1 reals that define a fully-generic hyperplane in D+1 space. Via a projective transform one could also view these N hyperplanes as the N hyperplanes tangent to the standard sphere in D+1 dimensions, at N generic points on that sphere surface. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (1)
-
Warren D Smith