We propose two algorithms for the planar Euclidean traveling salesman problem. The first runs in O(k!kn) time and O(k) space, and the second runs in O(2kk2n) time and O(2kkn) space, where n denotes the number of input points and k denotes the number of points interior to the convex hull.
Deineko, V. G., Hoffmann, M., Okamoto, Y., & Woeginger, G. J. (2006). The traveling salesman problem with few inner points. Operations Research Letters, 34(1), 106-110. https://doi.org/10.1016/j.orl.2005.01.002