CoBarS: Fast reweighted sampling for polygon spaces in any dimension (Q6624424)

In the paper, the authors consider configurations of \(n\) points in \(\mathbb{R}^d\) with positions \(v_1, \ldots, v_n\) separated by a length vector \(r\) of fixed distances \(r_1, \ldots, r_n > 0\). Because indices are treated cyclically, so the displacement vectors can be defined as \(v_{i+1} - v_i = r_i x_i\), where \(x_i\) is a unit vector in \(\mathbb{R}^d\). The elements of such space are polygons with edge lengths given by the \(r_i\). The goal of the paper is then to introduce an efficient way of randomly sampling such polygons.\N\NThe authors start by observing that it is easy to construct configurations of \(n + 1\) points \(v_1, \ldots, v_{n+1}\) so that \(|v_{i+1} - v_i| = r_i\) by sampling unit vectors \(x_i\) uniformly from a product of spheres and letting \(v_i = \sum_{j < i} r_j x_j\). These configurations have the correct edge lengths, but they usually fail to close because \(v_{n+1} = v_1\) is satisfied if and only if \(\sum_{i=1}^{n} r_i x_i = 0\). However, the authors build a map from the space of open polygons to the space of closed polygons using the conformal barycenter. This map is only defined implicitly but can be computed efficiently using an algorithm introduced by the authors in [SIAM J. Appl. Algebra Geom. 6, No. 3, 503--530 (2022; Zbl 1515.65051)]. This gives a fast sampling algorithm with \(\mathcal{O}(n)\) time, but the resulting samples are biased.\N\NNext, the authors propose a fast and explicit way to compute reweighting factors, which eliminates the sampling bias. The reweighting factors adjust the resulting distribution to match standard probability measures on the space of closed polygons. These reweighting factors can also be computed in \(\mathcal{O}(n)\) time for a fixed dimension. Experimental results demonstrate that the CoBarS algorithm is both efficient and accurate in practice. An open-source reference implementation is available, providing a practical tool for applications requiring random sampling of polygon configurations.