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.