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)