CoBarS: Fast reweighted sampling for polygon spaces in any dimension

Abstract

We present the first algorithm for sampling random configurations of closed $n$-gons with any fixed edgelengths $r_1,\dots ,r_n$ in any dimension $d$ which is proved to sample correctly from standard probability measures on these spaces. We generate open $n$-gons as weighted sets of edge vectors on the unit sphere and close them by taking a Möbius transformation of the sphere which moves the center of mass of the edges to the origin. Using previous results of the authors, such a Möbius transformation can be found in $O(n)$ time. The resulting closed polygons are distributed according to a pushforward measure. The main contribution of the present paper is the explicit calculation of reweighting factors which transform this pushforward measure to any one of a family of standard measures on closed polygon space, including the symplectic volume for polygons in ${\mathbb{R}}^3$. For fixed dimension, these reweighting factors may be computed in $O(n)$ time. Experimental results show that our algorithm is efficient and accurate in practice, and an open-source reference implementation is provided.

27 pages, 8 figures