Given an $n$-element set $C\subseteq\mathbb{ R}^d$ and a (sufficiently generic) $k$-element multiset $V\subseteq\mathbb{ R}^d$, we can order the points in $C$ by ranking each point $c\in C$ according to the sum of the distances from $c$ to the points of $V$. Let $\Psi_k(C)$ denote the set of orderings of $C$ that can be obtained in this manner as $V$ varies, and let $\psi^{ \mathrm{ max}}_{ d,k}(n)$ be the maximum of $\lvert\Psi_k(C)\rvert$ as $C$ ranges over all $n$-element subsets of $\mathbb{ R}^d$. We prove that $\psi^{ \mathrm{ max}}_{ d,k}(n)=\Theta_{ d,k}(n^{ 2dk})$ when $d \geq 2$ and that $\psi^{ \mathrm{ max}}_{ 1,k}(n)=\Theta_k(n^{ 4\lceil k/2\rceil -1})$. 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 $\Psi(C)=\bigcup_{ k\geq 1}\Psi_k(C)$; this includes an exact description of $\Psi(C)$ when $d=1$ and when $C$ is the set of vertices of a vertex-transitive polytope.
Categories: math.CO math.MG