Direct Sampling of Confined Polygons in Linear Time
Clayton Shonkwiler and Kandin Theis
我们介绍了一种在三个空间中采样紧密受限的随机等边封闭多边形的算法,该多边形在边缘数中具有运行时线性。 使用共称几何,采样这样的多边形减少到采样一个瞬间多顶,在我们的约束模型中,从组合的角度来看,这种多顶是非常自然的。 这种与组合学的联系产生了我们的快速采样算法和关于顶点到起源的预期距离的显式公式。 我们使用我们的算法来研究密闭多边形的预期总曲率,导致对总曲率的渐近进行了非常精确的猜想。
We present an algorithm for sampling tightly confined random equilateral closed polygons in three-space which has runtime linear in the number of edges. Using symplectic geometry, sampling such polygons reduces to sampling a moment polytope, and in our confinement model this polytope turns out to be very natural from a combinatorial point of view. This connection to combinatorics yields both our fast sampling algorithm and explicit formulas for the expected distances of vertices to the origin. W...