# geometry – Given N points in the Cartesian plane, how many unique sequences are formed by ordering them by distance from any arbitrary test point?

Let $$P$$ be a set of $$N$$ distinct points in the Cartesian plane $$C$$, and let $$S_P$$ be the set of all $$N$$-sequences of these Cartesian points; a particular sequence $$s$$ has elements $$s_1$$ through $$s_N$$.

Consider the subset of all sequences that that ordered with respect to some point in the Cartesian plane:
$$D(P) = { s in S_P mid textrm{for some } x in C, left| s_{k} – x right| leq left| s_{k+1} – x right| textrm{for all } 1 leq k < N }$$
My question is, is there an upper bound on the cardinality of $$D$$? Or, is there some asymptotic behavior for
$$D_N = max_{{ P subset C : left| P right| = N}} left| D(P) right|$$
that is stronger than $$O(N!)$$?

My feeling is that $$D_N sim O(N^2)$$; I might have heard or read this somewhere before but can’t recall the source. For a particular point $$x$$, let the set of sequences of points ordered by distance from $$x$$ be denoted $$x(P)$$ (below I’ll gloss over the fact that there can be more than one when distances are equal). The set $$P$$ determines a Voronoi diagram in the plane, with each point $$x$$ in a cell with its nearest neighbor $$p in P$$. For $$x$$ close enough to $$p$$, $$x(P) = p(P)$$. Once $$x$$ gets slightly further away, its next nearest neighbor may be distinct from $$p$$‘s nearest neighbor $$q$$. A simple 1 dimensional example:

q---p-x---r

The point $$x$$ is two units away from $$p$$ and four from $$r$$, but $$p$$ is closer to $$q$$ than $$r$$. I’m sure I could draw up cases where $$x$$‘s third nearest neighbor differ’s from $$p$$‘s second, and so on; however, it seems difficult to continue this forever and create a situation where $$x(P)$$ differs from $$p(P)$$ for its entire length (after the initial element where they must agree). Once the ordering reaches far enough away neighbors $$w$$, it seems that $$left|p-xright|$$ should (usually) be small compared to $$left|p-wright|$$. Of course, there are scenarios where that doesn’t hold (e.g. if one Voronoi cell is much larger than all others), so this isn’t a precise statement that I’m able to work into a rigorous argument.

It would also be interesting to know how this generalizes to other geometries.