let $P_0,\ldots, P_k\in \mathbb{R}^2$ be a set of points. Furthermore let $\epsilon\in \mathbb{R}$.
Now I am trying to find non-trivial lower and upper bounds for
$ \sum_{i=1}^k ||Q_i-Q_{i-1}||^2\quad \text{w.r.t.}\quad ||P_i-Q_i||\leq \epsilon\quad\text{for all} \quad i=0,\ldots,k $
I know there is the trivial bound $ \sum_{i=1}^k \left(||P_i-P_{i-1}||-2\epsilon\right)^2\leq\sum_{i=1}^k ||Q_i-Q_{i-1}||^2\leq \sum_{i=1}^k \left(||P_i-P_{i-1}||+2\epsilon\right)^2 $ (using the triangle inequality).
However, for most combinations of $P_i$, these bounds are rather weak. Do you know a better approach for getting a tight bound on that sum? Of course I could always use some numerical optimization, but then you have to trouble yourself with bracketing the minimum and maximum, which I would rather like to avoid. I would much prefer a clean geometric or analytical solution.
Thanks for your thoughts.
P.S.: I am having quite some trouble tagging this question to the right field, as it seems so elementary. You are welcome to set better tags than I did...
Edit 1
Two thoughts:
- You can show that it is either $P_i=Q_i$ or $||P_i-Q_i||=\epsilon$ when minimizing or maximizing the sum of squares
- You can write the problem as a quadratically constrained quadratic program. However, this seems so much trouble for such a small problem...