# 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:

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.

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$.

• The use of one of the heap variants is of course better than calculating the detours for each pair of insertion candidate and tour edge; what I had in mind, was something like a Voronoi Diagram. "Filling" the heap initially requires calculating the detours of each pair of candidate vertex and edge of the initial tour; that is however not necessary. The tours that are generated with the greedy least expansion are almost surely not simple for $n>50$ points that are iid in the unit square. I have implemented that strategy and was initially also convinced that it would generate simple polygons. – Manfred Weis Feb 10 '18 at 21:47
• @ManfredWeis: Yes, some Voronoi-diagram like structure would be necessary to beat quadratic time complexity. – Joseph O'Rourke Feb 11 '18 at 0:43