Computational Geometric Aspects of Greedy Tour Expansion 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.
 A: Let $P$ be the original set of points, and $P'$ those not yet in the tour.
Compute for each edge $e_i=(t_i,t_{i+1})$ the length increase if $e_i$ stretches
to each $p \in P'$. Store all these in a heap.
Take off the min stretch, say from $e_i$ to $p$, and insert $p$ into the
tour, and remove $p$ from $P'$. Now you need to remove from the heap all
those entries matching an edge $e_j$ to this $p$, as $p$ is no longer available.
So this costs $|P'|$. Next you need to insert into the heap new entries
for the two new edges $(t_i,p)$ and $(p,t_{i+1})$, matching with
each point in $P'$. This costs $\log |P'|$.
I think the overall cost is then $O(n^2 \log n)$, where $n=|P|$, 
likely not what you want.
Consider this the naive algorithm to improve.

          


          

Red point is incorporated into the tour.


It would be interesting to find an example that does not result in a simple polygon, or prove that the algorithm always does result in a simple polygon.


Added. This confirms Manfred's comment that the path can be non-simple.

          


          

A crossing path, $n=50$.


