论文标题
计算多层型的覆盖半径，并应用于孤独的跑步者
Computing the covering radius of a polytope with an application to lonely runners
论文作者
论文摘要
我们关注的是确定理性多层的覆盖半径的计算问题。该参数被定义为晶格所需的最小扩张因子，它翻译了相应扩张的层压板以覆盖整个空间。作为我们的主要结果，我们描述了一种针对此问题的新算法，该算法比Kannan（1992）的唯一算法更简单，更高效，更易于实施。在著名的孤独跑步者猜想的变体中，我们使用其几何解释来覆盖地质底座的半径，并应用我们的算法来证明三个具有单个起点的跑步者的开放式案例。
We are concerned with the computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed for the lattice translates of the correspondingly dilated polytope to cover the whole space. As our main result, we describe a new algorithm for this problem, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). Motivated by a variant of the famous Lonely Runner Conjecture, we use its geometric interpretation in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points.
