Euclidean TSP with Few Inner Points in Linear Space

DOI10.1007/978-3-319-13075-0_55zbMATH Open1433.68494arXiv1406.2154OpenAlexW2105572399MaRDI QIDQ2942672

Paweł Gawrychowski, Damian Rusak

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

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 when $k$ is significantly smaller than $n$, i.e., when there are just few inner points, works in $O(k^{11sqrtk}{k}^{1.5}{n}^3)$ time [Knauer and Spillner, WG 2006], but also requires space of order $k^{csqrtk}{n}^2$. The best linear space algorithm takes $O(k!kn)$ time [Deineko, Hoffmann, Okamoto, Woeginer, Oper. Res. Lett. 34(1), 106-110]. We construct a linear space $O(n{k}^2+k^{O(sqrtk)})$ 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. This argument also shows that the problem admits a quadratic bikernel.

Full work available at URL: https://arxiv.org/abs/1406.2154

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

Euclidean TSP in narrow strips ⋮ Non-crossing Hamiltonian paths and cycles in output-polynomial time

This page was built for publication: Euclidean TSP with Few Inner Points in Linear Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942672)