Computing the covering radius of a polytope with an application to lonely runners (Q2095112): Difference between revisions

The authors consider the computational problem of determining the covering radius of a rational polytope. They propose a faster and simpler algorithm than this by \textit{R. Kannan} [Combinatorica 12, No. 2, 161--177 (1992; Zbl 0753.11013)]. It is applied for proving the following theorem being a special case of the well known Lonely Runner Conjecture stated by \textit{J. M. Wills} [Monatsh. Math. 72, 254--263, 368--381 (1968; Zbl 0188.10602)]: \par Theorem. Consider three runners with pairwise distinct constant velocities, who start running on a circular track of length \(11\), with not necessarily identical starting positions. A stationary spectator watches the runners from a fixed position along the track. Then, there exists a time at which all the runners have distance at least \(1/4\) from the spectator.