Drawing Hamiltonian cycles with no large angles (Q426910): Difference between revisions

Summary: Let \(n \geq 4\) be even. It is shown that every set \(S\) of \(n\) points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of \(n\) straight-line edges such that the angle between any two consecutive edges is at most \(2\pi/3\). For \(n=4\) and 6, this statement is tight. It is also shown that every even-element point set \(S\) can be partitioned into at most two subsets, \(S_1\) and \(S_2\), each admitting a spanning tour with no angle larger than \(\pi/2\). \textit{S. P. Fekete} and \textit{G. J. Woeginger} [Comput. Geom. 8, No. 4, 195--218 (1997; Zbl 1133.90385)] conjectured that for sufficiently large even \(n\), every \(n\)-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any \(\epsilon>0\), these sets almost surely admit a spanning tour with no angle larger than \(\epsilon\).