Low Discrepancy Constructions in the Triangle

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. S...

• Publication year

  2014

• Venue

  SIAM Journal on Numerical Analysis

• Publication date

  2014-03-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/140960463arXiv 1403.2649
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Random Number Generation and Quasi-Monte Carlo†

  2015cited by this paper
• A Koksma–Hlawka Inequality for Simplices

  2013influential reference
• Point Sets on the Sphere \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{S}^{2}$\end{document} with Small Spher

  2011cited by this paper
• Discrepancy with respect to convex polygons

  2007influential reference
• Transforming low-discrepancy sequences from a cube to a simplex

  2005influential reference
• Multidimensional variation for quasi-Monte Carlo

  2004influential reference
• Probability and measure theory

  1999influential reference
• Number-theoretic Methods in Statistics

  1996cited by this paper
• Stratified sampling of spherical triangles

  1995cited by this paper
• Randomly Permuted (t,m,s)-Nets and (t, s)-Sequences

  1995influential reference
• Lattice Methods for Multiple Integration

  1994cited by this paper
• Kronecker-type sequences and nonarchimedean diophantine approximations

  1993cited by this paper
• A survey of numerical cubature over triangles

  1993cited by this paper
• Random number generation and Quasi-Monte Carlo methods

  1992influential reference
• Non-Uniform Random Variate Generation

  1986cited by this paper
• On irregularities of distribution.

  1980cited by this paper
• Elementary classical analysis

  1974cited by this paper
• On Continued Fractions

  1972cited by this paper

• Constructive quasi-uniform sequences over triangles

  2025influential citation
• Application of quasi-Monte Carlo in Mine Countermeasure Simulations with a Stochastic Optimal Control Framework

  2025cites this paper
• Randomized Quasi-Monte Carlo Methods on Triangles: Extensible Lattices and Sequences

  2024influential citation
• PhysHand: A Hand Simulation Model with Physiological Geometry, Physical Deformation, and Accurate Contact Handling

  2024cites this paper
• IF-Garments: Reconstructing Your Intersection-Free Multi-Layered Garments from Monocular Videos

  2024cites this paper
• Uniform Distribution via Lattices: From Point Sets to Sequences

  2023cites this paper
• Quasi-Monte Carlo methods for mixture distributions and approximated distributions via piecewise linear interpolation

  2023cites this paper
• Local Optimization for Robust Signed Distance Field Collision

  2020cites this paper
• Optimization-based quasi-uniform spherical t-design and generalized multitaper for complex physiological time series

  2019cites this paper
• EC-tractability of approximation problems in function spaces defined over products of simplices

  2019cites this paper
• ASYMPTOTIC NORMALITY OF SCRAMBLED GEOMETRIC NET QUADRATURE BY KINJAL BASU1

  2017influential citation
• Quasi-Monte Carlo integration for twice differentiable functions over a triangle

  2017influential citation
• Analysis of Framelet Transforms on a Simplex

  2017influential citation
• Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences

  2017cites this paper
• Localized Tight Frames and Fast Framelet Transforms on the Simplex

  2017cites this paper
• Quasi-Monte Carlo for an Integrand with a Singularity along a Diagonal in the Square

  2016cites this paper
• Constrained Multi-Slot Optimization for Ranking Recommendations

  2016cites this paper
• Asymptotic Normality of Scrambled Geometric Net Quadrature

  2016cites this paper
• Scrambled Geometric Net Integration Over General Product Spaces

  2015cites this paper
• Density Estimation via Discrepancy

  2015cites this paper
• Low-discrepancy sequences for piecewise smooth functions on the two-dimensional torus

  2015cites this paper
• Transformations and Hardy-Krause Variation

  2015influential citation
• Density Estimation via Adaptive Partition and Discrepancy Control

  2014cites this paper
• A constructive theory of sampling for image synthesis using reproducing Kernel bases

  2014cites this paper
• Quasi-Monte Carlo tractability of high dimensional integration over products of simplices

  2014influential citation
• Density Estimation via Discrepancy Based Adaptive Sequential Partition

  2014cites this paper
• Functions of bounded variation, signed measures, and a general Koksma-Hlawka inequality

  2014cites this paper
• TRANSFORMATIONS AND HARDY – KRAUSE VARIATION

  year unknowncites this paper