Márton Naszódi: Computing the Covering Radius with an Application to the Lonely Runner Conjecture

Abstract: The covering radius of a convex body in R^d is the minimal dilation factor that is needed for the integer lattice translates of the dilated body to cover R^d. As our main result, we describe a new algorithm for computing this quantity for rational polytopes, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). We consider a geometric interpretation of the famous Lonely Runner Conjecture in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points.