Ordering Candidates via Vantage Points

Given an n-element set C⊆Rd and a (sufficiently generic) k-element multiset V⊆Rd, we can order the points in C by ranking each point c∈C according to the sum of the distances from c to the points of V. Let Ψk(C) denote the set of orderings of C that can be obtained in this manner as V varies, and let ψd,kmax(n) be the maximum of |Ψk(C)| as C ranges over all n-element subsets of Rd. We prove that ψd,kmax(n)=Θd,k(n2dk) when d≥2 and that ψ1,kmax(n)=Θk(n4⌈k/2⌉-2). As a step toward proving this result, we establish a bound on the number of sign patterns determined by a collection of functions that are sums of radicals of nonnegative polynomials; this can be understood as an analogue of a classical theorem of Warren. We also prove several results about the set Ψ(C)=⋃k≥1Ψk(C); this includes an exact description of Ψ(C) when d=1 and when C is the set of vertices of a vertex-transitive polytope.