Euclidean TSP with Few Inner Points in Linear Space

Abstract

Given a set of $n$ points in the Euclidean plane, such that just $k$ points are strictly inside the convex hull of the whole set, we want to find the shortest tour visiting every point. The fastest known algorithm for the version with few inner points, i.e., small $k$, works in $\mathcal {O}(k^{\mathcal {O}(\sqrt{k})}k^{1.5}n^{3})$ time [Knauer and Spillner, WG 2006], but also requires space of order $k^{\varTheta (\sqrt{k})}n^{2}$. The best linear space algorithm takes $\mathcal {O}(k!kn)$ time [Deineko, Hoffmann, Okamoto, Woeginer, Oper. Res. Lett. 34(1), 106-110]. We construct a linear space $\mathcal {O}(nk^2+k^{\mathcal {O}(\sqrt{k})})$ time algorithm. The new insight is extending the known divide-and-conquer method based on planar separators with a matching-based argument to shrink the instance in every recursive call.

Supported by the NCN grant 2011/01/D/ST6/07164.