Searching permutations for constructing uniformly distributed point sets

François Clément

doi:10.1073/pnas.2424464122

Searching permutations for constructing uniformly distributed point sets

2025-04-03

0

OA

AI

DOI：10.1073/pnas.2424464122

Original

Original request for help

Save

Abstract

En 中文

Uniformly distributed point sets of low discrepancy are heavily used in experimental design and across a very wide range of applications such as numerical integration, computer graphics, and finance. Recent methods based on Graph Neural Networks [T. K. Rusch, N. Kirk, M. M. Bronstein, C. Lemieux, D. Rus, Proc. Natl. Acad. Sci. U.S.A. 121, e2409913121 (2024).] and solver-based optimization identified point sets having much lower discrepancy than previously known constructions. We show in this note that further substantial improvements are possible by separating the construction of low-discrepancy point sets into i) the relative position of the points, and ii) the optimal placement respecting these relationships. Using tailored permutations, we construct point sets that are of 20% smaller discrepancy on average than those proposed by Rusch et al. In terms of inverse discrepancy, our sets reduce the number of points in dimension 2 needed to obtain a discrepancy of 0.005 from more than 500 points to less than 350. For applications where the sets are used to query time-consuming models, this is a significant reduction.

Keywords:

discrepancy

optimization

permutations

Searching permutations for constructing uniformly distributed point sets

Abstract

Journal

Organization