Searching permutations for constructing uniformly distributed point sets

• 成果类型: Article
• 署名作者: Clement, Francois; Doerr, Carola; Klamroth, Kathrin; Paquete, Luis
• 署名单位: University of Washington; University of Washington Seattle; Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; University of Wuppertal; Universidade de Coimbra
• 刊物名称: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
• ISSN/ISSBN: 0027-11979
• DOI: 10.1073/pnas.2424464122
• 发表日期: 2025-04-03

摘要

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.