Douglas-Peucker line simplification algorithm time complexity
Your analysis seems correct, except for that you need $T(n)=T(index)+T(n-index+1)+2n$ instead because when $index$ is either $0$ or $n-1$ you won't get in the right hand side another factor of $T(n)$, which is not allowed.
In fact, it will yield something very close to the recurrence of the running time in the quicksort algorithm.
Worst case scenario
When index is either $0$ or $n-1$, the recurrence will boil down to $T(n)=T(1)+T(n-1)+2n = T(n-1) + (2n + T(1))$. You can easily show by induction that $T(n)=\Theta(n^2)$ in this case.
Best case scenario
We assume the input in the recursion will always be cut down by half. That is, the recursion is $T(n)=2T(n/2)+2n$.
Define $b=a=2$ and $f(n)=2n$. Then, $T(n)=aT(n/b)+f(n)$.
We can calculate $c_{crit}=\log_{b}(a)=\log_2(2)=1$ and thus $f(n)=2n=\Theta(n)=\Theta(n^{c_{crit}})$.
Now we can directly use the second case to get that $T(n)=\Theta(n^{c_{crit}}\log(n))=\Theta(n\log(n))=O(n^2)$
Average case scenario
If we assume that the input is a random variable, such that the choice of $index$ is uniformly distributed in $\{0,\dots,n-1\}$, then the algorithm takes expected time $\Theta(n\log(n))$. Take a look at the proof for quicksort to see how its done.