Low Discrepancy Constructions in the Triangle

Abstract

Most quasi-Monte Carlo research focuses on sampling from the unit cube. Many problems, especially in computer graphics, are defined via quadrature over the unit triangle. Quasi-Monte Carlo methods for the triangle have been developed by Pillards and Cools [J. Comput. Appl. Math., 174 (2005), pp. 29--42] and by Brandolini et al. [``A Koksma--Hlawka inequality for simplices," in Trends in Harmonic Analysis, Springer, 2013, pp. 33--46]. This paper presents two quasi-Monte Carlo constructions in the triangle with a vanishing discrepancy. The first is a version of the van der Corput sequence customized to the unit triangle. It is an extensible digital construction that attains a discrepancy below $12/{\sqrt{N}}$. The second construction rotates an integer lattice through an angle whose tangent is a quadratic irrational number. It attains a discrepancy of $O(\log(N)/N),$ which is the best possible rate. Previous work strongly indicated that such a discrepancy was possible, but no constructions were available. Scrambling the digits of the first construction improves its accuracy for integration of smooth functions. Both constructions also yield convergent estimates for integrands that are Riemann integrable on the triangle without requiring bounded variation.