Has the following problem already been investigated from the Computational Geometry point of view and what are the results regarding worst case complexity?
Given
- a finite set $\mathcal{P}$ of $n$ distinct points in the Euclidean plane,
- its convex hull $\mathcal{T_{\text{card(CH(}\mathcal{P}\text{))}}}\ :=\ \text{CH(}\mathcal{P}\text{)}$ as the initial tour.
while $m<n$
- chose $\ \left( p\in\mathcal{P}\setminus\mathcal{T_m},\ t_i\in\mathcal{T_m}\right):$
$\quad\quad\quad\|p-t_i\|+\|t_{\text{succ(}i\text{)}}-p\|-\|t_{\text{succ(}i\text{)}}-t_i\|$ $\quad\le\quad\|q-t_k\|+\|t_{\text{succ(}k\text{)}}-q\|-\|t_{\text{succ(}k\text{)}}-t_k\|$
$\forall q\in\mathcal{P}\setminus\mathcal{T_m},\quad\left(t_k,t_{\text{succ(}k\text{)}}\right)\in\mathcal{T_m}$- $\mathcal{T_{m+1}} := \lbrace\mathcal{T_m}\setminus\left(t_{\text{i}},t_{\text{succ(}i\text{)}}\right)\rbrace\cup\lbrace\left(t_i,p\right),\left(p,t_{\text{succ(}i\text{)}}\right)\rbrace$
in this context, $t_{\text{succ(}i\text{)}}$ shall denote the tour-vertex that is encountered immediately after vertex $t_\text{i}$ when traversing the tour w.l.o.g in counter clockwise order.
Please note, that the objective of the task is not to create a simple polygon through all points or even an optimal tour; it is rather to determine the point, whose integration into the tour incurs the least length-increase, as fast as possible.
I am looking for techniques from Computational Geometry, i.e. algorithms and datastructures, that bring about provable improvements beyond updating least detour information w.r.t. the newly generated edges after the insertion of a further point.
Here is an example of a selfintersecting tour with 50 points, that was generated with the greedy insertion algorithm, answering a question of Joseph O'Rourke:
Addendum 2018-02-11:
to indicate, that geometric concepts may indeed be promising, consider the problem of deciding, whether a point $p\notin \mathcal{T_i}$ is closer (in the sense of incurred elongation) to tour edge $(t_i,t_j)$ or to $(t_j,t_k)$.
in that special case, where the tour edges are adjacent, the separator equals the radical axis of the circles with center and radius $(t_i,\|t_j-t_i\|)$ and $(t_k,\|t_k-t_j\|)$; whether that is an actual improvement, depends of course on the computational model and the limitations on available resources - for very large instances it may not be viable to store all distances between pairs of points, whence deciding on which side of the radical line a point lies, is cheaper than calculating and comparing two detours.
for non-adjacent tour edges the situation is not so simple and yields non-linear algebraic curves as separators in general.