On Low Discrepancy Samplings in Product Spaces of Motion Groups

Original · EN

Deterministically generating near-uniform point samplings of the motion groups like SO(3), SE(3) and their n-wise products SO(3)ⁿ, SE(3)ⁿ is fundamental to numerous applications in computational and data sciences. The natural measure of sampling quality is discrepancy. In this work, our main goal is construct low discrepancy deterministic samplings in product spaces of the motion groups. To this end, we develop a novel strategy (using a two-step discrepancy construction) that leads to an almost exponential improvement in size (from the trivial direct product). To the best of our knowledge, this is the first nontrivial construction for SO(3)ⁿ, SE(3)ⁿ and the hypertorus Tⁿ. We also construct new low discrepancy samplings of S² and SO(3). The central component in our construction for SO(3) is an explicit construction of N points in S² with discrepancy Ø(1/√N) with respect to convex sets, matching the bound achieved for the special case of spherical caps in ABD₁2. We also generalize the discrepancy of Cartesian product sets Chazelle04thediscrepancy to the discrepancy of local Cartesian product sets. The tools we develop should be useful in generating low discrepancy samplings of other complicated geometric spaces.