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!)$?
[EDIT: to rule out some cases where a point is equally near all points in the plane and trivially $\left| D(P) \right| = N!$, as pointed out by @HagenvonEitzen, this definition can be made more interesting by restricting $D(P)$ to uniquely ordered sequences:
$$D'(P) = \{ s \in S_P \mid \textrm{for some } x \in C, \left| s_{k} – x \right| < \left| s_{k+1} – x \right| \textrm{for all } 1 \leq k < N \}$$.
The set of points $x$ forming sequences in $D(P)$ but not $D'(P)$ must be equidistant to at least two points in $P$ and are therefore constrained to lie on some collection of lines, and thus have measure zero.
]
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-x\right|$ should (usually) be small compared to $\left|p-w\right|$. 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.
Best Answer
With the definition of $D(P)$ in the OP, we can let $P$ be a set of $n$ points on a circle; then thr centre of the circle witnesses that $D(P)$ is the set of all $n!$ permutations of $P$. Thus $$D_n = n!.$$
Let us adjust $D$ to allow only points in general position, i.e., $$D(P) = \{ s \in S_P \mid \textrm{for some } x \in C, \left| s_{k} - x \right| < \left| s_{k+1} - x \right| \textrm{for all } 1 \leq k < N \}.$$ Now we can show $$ D_n=O(n^4)$$ (and can perhaps be improved). Indeed, we must pick $x$ in any of the regions that the plane is cut into by the $m={n\choose 2}$ perpendicular bisectors between points in $P$, and it is well-known that the maximal number of regions obtainable with $m$ lines is ${m+1\choose 2}+1$. As we are not free in the choice of our $m$ lines, I suspect that lowering the exponent is still possible.