3
$\begingroup$

Consider $n$ points $x_1,\ldots,x_n$ on the unit circle $S^1\subset \mathbb{C}$. Suppose these are ordered such that $\sum_{i=1}^n |x_i-x_{i+1}|$ (indices modulo $n$) is maximal for all possible permutation of indices, i.e. going from $x_1$ to $x_2$ to $x_3$ ... to $x_n$ to $x_1$ on straight lines in the complex plane describes the longest possible path to visit each $x_i$ exactly once. Let $c_i:=|x_i-x_{i+1}|$ for $i=1\ldots n$ and $\sigma$ a permutation such that $$c_{\sigma(1)}\geq c_{\sigma(2)}\geq \ldots \geq c_{\sigma(n)}.$$

For an arbitrary point $z\in S^1$ define $d_i:=d_{z,i}:=|z-x_i|$ and let $\tau:=\tau_z$ be a permutation such that $$d_{\tau(1)}\geq d_{\tau(2)}\geq \ldots \geq d_{\tau(n)}.$$

The question is: Is there a choice for $z$ such that for all $i=1\ldots n$ the inequalities $d_{\tau(i)}\leq c_{\sigma(i)}$ hold?

$\endgroup$
1
$\begingroup$

Sometimes yes and sometimes no. If the $x_i$ are an odd number of equally spaced points then all the $c_i$ are equal and less than $d_{ \tau(1)}$ (whatever $z$ is.) However if the $x_i$ are an even number of points tightly clustered half each at the top and bottom then all the $c_i$ will be nearly $2$ (the diameter) but a $z$ near the middle will have all the $d$ about $\sqrt{2}.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Right, that's the basic kind of example one might think of. I don't get your first point, though. If the $x_i$ are equally spaced, then for $z=x_j$ we have $d_{\tau(1)}=|x_j-x_k|$ for some $k$ and hence $d_{\tau(1)}\leq c_i$ for all $i$. ($z=x_j$ should be allowed.) $\endgroup$ – Abel Stolz Dec 22 '12 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.