The shortest path or cycle through given planar points (the solution to the traveling salesperson problem) never crosses itself: any crossing can be eliminated by a local move that shortens the tour. One might think that, correspondingly, the longest path or cycle through enough planar points always crosses itself. We show that this is not the case: there exist arbitrarily large point sets for which the longest path or cycle has no crossing.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.