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$. Fekete and Woeginger 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$.
@article{10_37236_2356,
author = {Adrian Dumitrescu and J\'anos Pach and G\'eza T\'oth},
title = {Drawing {Hamiltonian} cycles with no large angles},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2356},
zbl = {1243.05138},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2356/}
}
TY - JOUR
AU - Adrian Dumitrescu
AU - János Pach
AU - Géza Tóth
TI - Drawing Hamiltonian cycles with no large angles
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2356/
DO - 10.37236/2356
ID - 10_37236_2356
ER -
%0 Journal Article
%A Adrian Dumitrescu
%A János Pach
%A Géza Tóth
%T Drawing Hamiltonian cycles with no large angles
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2356/
%R 10.37236/2356
%F 10_37236_2356
Adrian Dumitrescu; János Pach; Géza Tóth. Drawing Hamiltonian cycles with no large angles. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2356
