SU\G(𝔸)/K·U
Sign Up for free Log In

Constructing optimal star discrepancy sets

Authors

François Clément, Carola Doerr, Kathrin Klamroth, Luís Paquete
Type: Article
Publication Date: 2025-05-02
Citations: 0
DOI: https://doi.org/10.1090/bproc/254

Abstract

We provide in this paper a constructive proof of optimal <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript normal infinity"> <mml:semantics> <mml:msub> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">∞</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">L_{\infty }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> star discrepancy values in dimension 2 for up to 21 points and up to 8 points in dimension 3. This extends work by White (Numer. Math. <bold>27</bold> (1976/77), no. 2, 157–164) for up to six points in dimension 2 and of Larcher and Pillichshammer (J. Comput. Appl. Math. <bold>206</bold> (2007), no. 2, 977–985) for two points in arbitrary dimensions. We show that these optimal sets have a far lower discrepancy than the previous references and, perhaps more importantly, present a very different structure.

Topics

Locations

  • Proceedings of the American Mathematical Society Series B
    View

On the inverse of the star-discrepancy

2012-01-01
Christoph Aistleitner
The inverse of the star-discrepancy $N^*(d,\ve)$ denotes the smallest possible cardinality of a set of points in $[0,1]^d$ achieving a star-discrepancy of at most $\ve$. By a result of Heinrich, … The inverse of the star-discrepancy $N^*(d,\ve)$ denotes the smallest possible cardinality of a set of points in $[0,1]^d$ achieving a star-discrepancy of at most $\ve$. By a result of Heinrich, Novak, Wasilkowski and Wo{ź}niakowski, $$ N^*(d,\ve) \leq c_{\textup{abs}} d \ve^{-2}. $$ Here the dependence on the dimension $d$ is optimal, while the precise dependence on $\ve$ is an open problem. In the present paper we prove that $$ N^*(d,\ve) \leq c_{\textup{abs}} d \ve^{-3/2} (\log (\ve^{-1}))^{1/2}. $$ This is a surprising result, which disproves a conjecture of Novak and Wo{ź}niakowski.

Constructing Optimal $L_{\infty}$ Star Discrepancy Sets

2023-01-01
François Clément , Carola Doerr , Kathrin Klamroth +1 more
The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a … The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a very hard problem in the discrepancy community. Indeed, optimal point sets are, up to now, known only for $n\leq 6$ in dimension 2 and $n \leq 2$ for higher dimensions. We introduce in this paper mathematical programming formulations to construct point sets with as low $L_{\infty}$ star discrepancy as possible. Firstly, we present two models to construct optimal sets and show that there always exist optimal sets with the property that no two points share a coordinate. Then, we provide possible extensions of our models to other measures, such as the extreme and periodic discrepancies. For the $L_{\infty}$ star discrepancy, we are able to compute optimal point sets for up to 21 points in dimension 2 and for up to 8 points in dimension 3. For $d=2$ and $n\ge 7$ points, these point sets have around a 50% lower discrepancy than the current best point sets, and show a very different structure.

Improving a Constant in High-Dimensional Discrepancy Estimates

2018-01-01
Hendrik Pasing , Christian Weiß
For all $s \geq 1$ and $N \geq 1$ there exist sequences $(z_1,\ldots,z_N)$ in $[0,1]^s$ such that the star-discrepancy of these points can be bounded by $$D_N^*(z_1,\ldots,z_N) \leq c \frac{\sqrt{s}}{\sqrt{N}}.$$ … For all $s \geq 1$ and $N \geq 1$ there exist sequences $(z_1,\ldots,z_N)$ in $[0,1]^s$ such that the star-discrepancy of these points can be bounded by $$D_N^*(z_1,\ldots,z_N) \leq c \frac{\sqrt{s}}{\sqrt{N}}.$$ The best known value for the constant is $c=10$ as has been calculated by Aistleitner in \cite{Ais11}. In this paper we improve the bound to $c=9$.
View PDF Chat

Improving a Constant in High-Dimensional Discrepancy Estimates

2018-10-26
Hendrik Pasing , Christian Weiß
For all $s \geq 1$ and $N \geq 1$ there exist sequences $(z_1,\ldots,z_N)$ in $[0,1]^s$ such that the star-discrepancy of these points can be bounded by $$D_N^*(z_1,\ldots,z_N) \leq c \frac{\sqrt{s}}{\sqrt{N}}.$$ … For all $s \geq 1$ and $N \geq 1$ there exist sequences $(z_1,\ldots,z_N)$ in $[0,1]^s$ such that the star-discrepancy of these points can be bounded by $$D_N^*(z_1,\ldots,z_N) \leq c \frac{\sqrt{s}}{\sqrt{N}}.$$ The best known value for the constant is $c=10$ as has been calculated by Aistleitner in \cite{Ais11}. In this paper we improve the bound to $c=9$.

Calculation of Discrepancy Measures and Applications

2014-01-01
Carola Doerr , Michael Gnewuch , Magnus Wahlström
View PDF Chat

Good Lattice Rules with a Composite Number of Points Based on the Product Weighted Star Discrepancy

2007-12-28
Vasile Sinescu , Stephen Joe

An elementary proof of a lower bound for the inverse of the star discrepancy

2022-01-01
Stefan Steinerberger
A central problem in discrepancy theory is the challenge of evenly distributing points $\left\{x_1, \dots, x_n \right\}$ in $[0,1]^d$. Suppose a set is so regular that for some $\varepsilon> 0$ … A central problem in discrepancy theory is the challenge of evenly distributing points $\left\{x_1, \dots, x_n \right\}$ in $[0,1]^d$. Suppose a set is so regular that for some $\varepsilon> 0$ and all $y \in [0,1]^d$ the sub-region $[0,y] = [0,y_1] \times \dots \times [0,y_d]$ contains a number of points nearly proportional to its volume and $$\forall~y \in [0,1]^d \qquad \left| \frac{1}{n} \# \left\{1 \leq i \leq n: x_i \in [0,y] \right\} - \mbox{vol}([0,y]) \right| \leq \varepsilon,$$ how large does $n$ have to be depending on $d$ and $\varepsilon$? We give an elementary proof of the currently best known result, due to Hinrichs, showing that $n \gtrsim d \cdot \varepsilon^{-1}$.

The weighted star discrepancy of Korobov’s $p$-sets

2015-05-07
Josef Dick , Friedrich Pillichshammer
We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these … We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these sets have largely been ignored since a number of other constructions have been discovered which achieve a better convergence rate. However, it has recently been discovered that the $p$-sets perform well in terms of the dependence on the dimension. We prove bounds on the weighted star discrepancy of the $p$-sets which hold for any choice of weights. For product weights, we give conditions under which the discrepancy bounds are independent of the dimension $s$. This implies strong polynomial tractability for the weighted star discrepancy. We also show that a very weak condition on the product weights suffices to achieve polynomial tractability.
View PDF Chat

Some open problems concerning the star-discrepancy

2003-03-25
Stefan Heinrich

The weighted star discrepancy of Korobov's $p$-sets

2014-01-01
Josef Dick , Friedrich Pillichshammer
We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these … We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these sets have largely been ignored since a number of other constructions have been discovered which achieve a better convergence rate. However, it has recently been discovered that the $p$-sets perform well in terms of the dependence on the dimension. We prove bounds on the weighted star discrepancy of the $p$-sets which hold for any choice of weights. For product weights we give conditions under which the discrepancy bounds are independent of the dimension $s$. This implies strong polynomial tractability for the weighted star discrepancy. We also show that a very weak condition on the product weights suffices to achieve polynomial tractability.

The weighted star discrepancy of Korobov's $p$-sets

2014-04-01
Josef Dick , Friedrich Pillichshammer
We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these … We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these sets have largely been ignored since a number of other constructions have been discovered which achieve a better convergence rate. However, it has recently been discovered that the $p$-sets perform well in terms of the dependence on the dimension. We prove bounds on the weighted star discrepancy of the $p$-sets which hold for any choice of weights. For product weights we give conditions under which the discrepancy bounds are independent of the dimension $s$. This implies strong polynomial tractability for the weighted star discrepancy. We also show that a very weak condition on the product weights suffices to achieve polynomial tractability.

Heuristic approaches to obtain low-discrepancy point sets via subset selection

2024-03-16
François Clément , Carola Doerr , Luís Paquete
Building upon the exact methods presented in our earlier work [J. Complexity, 2022], we introduce a heuristic approach for the star discrepancy subset selection problem. The heuristic gradually improves the … Building upon the exact methods presented in our earlier work [J. Complexity, 2022], we introduce a heuristic approach for the star discrepancy subset selection problem. The heuristic gradually improves the current-best subset by replacing one of its elements at a time. While the heuristic does not necessarily return an optimal solution, we obtain very promising results for all tested dimensions. For example, for moderate sizes 30≤n≤240, we obtain point sets in dimension 6 with L∞ star discrepancy up to 35% better than that of the first n points of the Sobol' sequence. Our heuristic works in all dimensions, the main limitation being the precision of the discrepancy calculation algorithms. We provide a comparison with a recent energy functional introduced by Steinerberger [J. Complexity, 2019], showing that our heuristic performs better on all tested instances. Finally, our results and complementary experiments also give further empirical information on inverse star discrepancy conjectures.
View PDF Chat

Component-by-component construction of low-discrepancy point sets of small size

2008-07-01
Benjamin Doerr , Michael Gnewuch , Peter Kritzer +1 more
Abstract We investigate the problem of constructing small point sets with low star discrepancy in the s -dimensional unit cube. The size of the point set shall always be polynomial … Abstract We investigate the problem of constructing small point sets with low star discrepancy in the s -dimensional unit cube. The size of the point set shall always be polynomial in the dimension s . Our particular focus is on extending the dimension of a given low-discrepancy point set. This results in a deterministic algorithm that constructs N -point sets with small discrepancy in a component-by-component fashion. The algorithm also provides the exact star discrepancy of the output set. Its run-time considerably improves on the run-times of the currently known deterministic algorithms that generate low-discrepancy point sets of comparable quality. We also study infinite sequences of points with infinitely many components such that all initial subsegments projected down to all finite dimensions have low discrepancy. To this end, we introduce the inverse of the star discrepancy of such a sequence, and derive upper bounds for it as well as for the star discrepancy of the projections of finite subsequences with explicitly given constants. In particular, we establish the existence of sequences whose inverse of the star discrepancy depends linearly on the dimension.
View PDF Chat

A note on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e49" altimg="si8.svg"><mml:mrow><mml:mo>(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>t</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>-weak tractability of the weighted star discrepancy of regular grids

2021-03-06
Jie Zhang

An Intermediate Bound on the Star Discrepancy

2012-01-01
Stephen Joe

On optimal extreme-discrepancy point sets in the square

1977-06-01
Brian E. White

Explicit constructions of point sets and sequences with low discrepancy

2013-01-01
Josef Dick , Friedrich Pillichshammer
In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of $\mathcal{L}_q$ discrepancy. In 1954 Roth proved a lower … In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of $\mathcal{L}_q$ discrepancy. In 1954 Roth proved a lower bound for the $\mathcal{L}_2$ discrepancy of finite point sets in the unit cube of arbitrary dimension. Later various authors extended Roth's result to lower bounds also for the $\mathcal{L}_q$ discrepancy and for infinite sequences. While it was known already from the early 1980s on that Roth's lower bound is best possible in the order of magnitude, it was a longstanding open question to find explicit constructions of point sets and sequences with optimal order of $\mathcal{L}_2$ discrepancy. This problem was solved by Chen and Skriganov in 2002 for finite point sets and recently by the authors of this article for infinite sequences. These constructions can also be extended to give optimal order of the $\mathcal{L}_q$ discrepancy of finite point sets for $q \in (1,\infty)$. The main aim of this article is to give an overview of these constructions and related results.
View PDF Chat

Explicit constructions of point sets and sequences with low discrepancy

2014-07-25
Josef Dick , Friedrich Pillichshammer
In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of $\mathcal{L}_q$ discrepancy. In 1954 Roth proved a lower … In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of $\mathcal{L}_q$ discrepancy. In 1954 Roth proved a lower bound for the $\mathcal{L}_2$ discrepancy of finite point sets in the unit cube of arbitrary dimension. Later various authors extended Roth's result to lower bounds also for the $\mathcal{L}_q$ discrepancy and for infinite sequences. While it was known already from the early 1980s on that Roth's lower bound is best possible in the order of magnitude, it was a longstanding open question to find explicit constructions of point sets and sequences with optimal order of $\mathcal{L}_2$ discrepancy. This problem was solved by Chen and Skriganov in 2002 for finite point sets and recently by the authors of this article for infinite sequences. These constructions can also be extended to give optimal order of the $\mathcal{L}_q$ discrepancy of finite point sets for $q \in (1,\infty)$. The main aim of this article is to give an overview of these constructions and related results.
View PDF Chat

Explicit constructions of point sets and sequences with low discrepancy

2013-08-20
Josef Dick , Friedrich Pillichshammer
In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of $\mathcal{L}_q$ discrepancy. In 1954 Roth proved a lower … In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of $\mathcal{L}_q$ discrepancy. In 1954 Roth proved a lower bound for the $\mathcal{L}_2$ discrepancy of finite point sets in the unit cube of arbitrary dimension. Later various authors extended Roth's result to lower bounds also for the $\mathcal{L}_q$ discrepancy and for infinite sequences. While it was known already from the early 1980s on that Roth's lower bound is best possible in the order of magnitude, it was a longstanding open question to find explicit constructions of point sets and sequences with optimal order of $\mathcal{L}_2$ discrepancy. This problem was solved by Chen and Skriganov in 2002 for finite point sets and recently by the authors of this article for infinite sequences. These constructions can also be extended to give optimal order of the $\mathcal{L}_q$ discrepancy of finite point sets for $q \in (1,\infty)$. The main aim of this article is to give an overview of these constructions and related results.

A Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy

2011-03-10
Michael Gnewuch , Magnus Wahlström , Carola Winzen
We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. Anal. 34 … We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. Anal. 34 (1997), 2028--2042] it is based on the optimization algorithm threshold accepting. Our improvements include, amongst others, a non-uniform sampling strategy which is more suited for higher-dimensional inputs, and rounding steps which transform axis-parallel boxes, on which the discrepancy is to be tested, into \emph{critical test boxes}. These critical test boxes provably yield higher discrepancy values, and contain the box that exhibits the maximum value of the local discrepancy. We provide comprehensive experiments to test the new algorithm. Our randomized algorithm computes the exact discrepancy frequently in all cases where this can be checked (i.e., where the exact discrepancy of the point set can be computed in feasible time). Most importantly, in higher dimension the new method behaves clearly better than all previously known methods.
View PDF Chat

Calculation of Discrepancy Measures and Applications

2014-01-01
Carola Doerr , Michael Gnewuch , Magnus Wahlström
View PDF Chat

Minimizing the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si22.gif" overflow="scroll"><mml:msub><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si23.gif" overflow="scroll"><mml:msub><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mo>∞</mml:mo></mml:mrow></mml:msub></mml:math> star discrepancies of a single point in the unit hypercube

2005-12-28
Tim Pillards , Bart Vandewoestyne , Ronald Cools

Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy

2007-10-02
Michael Gnewuch

On optimal extreme-discrepancy point sets in the square

1977-06-01
Brian E. White

The inverse of the star-discrepancy depends linearly on the dimension

2001-01-01
Stefan Heinrich , Henryk Woźniakowski , Grzegorz W. Wasilkowski +1 more
We study bounds on the classical ∗-discrepancy and on its inverse. Let n∞(d, e) be the inverse of the ∗-discrepancy, i.e., the minimal number of points in dimension d with … We study bounds on the classical ∗-discrepancy and on its inverse. Let n∞(d, e) be the inverse of the ∗-discrepancy, i.e., the minimal number of points in dimension d with the ∗-discrepancy at most e. We prove that n∞(d, e) depends linearly on d and at most quadratically on e−1. We present three upper bounds on n∞(d, e), all of them are based on probabilistic arguments and therefore they are non-constructive. The linear in d upper bound directly follows from deep results of the theory of empirical processes but it contains an unknown multiplicative factor. Two other upper bounds are without unknown factors but do not yield the linear (in d) upper bound. One upper bound is based on an average case analysis for the Lp-star discrepancy and our numerical results seem to indicate that it gives the best estimates for specific values of d and e. We also present two lower bounds on n∞(d, e). For lower bounds, we allow arbitrary coefficients in the discrepancy formula. We prove that n∞(d, e) must be of order d log e−1 and, roughly, of order dλe−(1−λ) for any λ ∈ (0, 1).
View PDF Chat

Discrepancy and convex programming

1972-12-01
Harald Niederreiter
View PDF Chat

Translations of nets and relationship between supreme andL ?-discrepancies

1996-01-01
Vsevolod F. Lev

Fibonacci sets and symmetrization in discrepancy theory

2011-08-21
Dmitriy Bilyk , Vladimir Temlyakov , Rui Yu

Component-by-component construction of low-discrepancy point sets of small size

2008-07-01
Benjamin Doerr , Michael Gnewuch , Peter Kritzer +1 more
Abstract We investigate the problem of constructing small point sets with low star discrepancy in the s -dimensional unit cube. The size of the point set shall always be polynomial … Abstract We investigate the problem of constructing small point sets with low star discrepancy in the s -dimensional unit cube. The size of the point set shall always be polynomial in the dimension s . Our particular focus is on extending the dimension of a given low-discrepancy point set. This results in a deterministic algorithm that constructs N -point sets with small discrepancy in a component-by-component fashion. The algorithm also provides the exact star discrepancy of the output set. Its run-time considerably improves on the run-times of the currently known deterministic algorithms that generate low-discrepancy point sets of comparable quality. We also study infinite sequences of points with infinitely many components such that all initial subsegments projected down to all finite dimensions have low discrepancy. To this end, we introduce the inverse of the star discrepancy of such a sequence, and derive upper bounds for it as well as for the star discrepancy of the projections of finite subsequences with explicitly given constants. In particular, we establish the existence of sequences whose inverse of the star discrepancy depends linearly on the dimension.
View PDF Chat

Low-Discrepancy Sequences

1997-08-31
Silvio Galanti , Alan Jung
<h3></h3> It has been estimated that malnutrition affects 50% of hospice patients. Nutritional assessment and support is vital in palliative care, since inadequate hydration and nutrition results in skin and … <h3></h3> It has been estimated that malnutrition affects 50% of hospice patients. Nutritional assessment and support is vital in palliative care, since inadequate hydration and nutrition results in skin and muscle wasting, vulnerability to the development of pressure ulcers, and susceptibility to infection. <h3>Method</h3> Clinical and catering staff established a nutritional steering group with the brief of introducing an assessment tool and improving the evaluation and management of nutritional risk in the hospice. The group identified several nutritional assessment tools and concluded that none were ideal for use in the hospice setting. The Nutritional Screening Tool was adapted to identify significant risk of nutritional problems in inpatients. The group devised a new policy and procedure for nutritional care along with an information leaflet for patients and families to support them in managing their own nutritional risk. Inpatients were given the opportunity to choose meals, snacks and drinks. Training for all staff on nutritional assessment using the tool and management of nutritional risk was provided <h3>Results</h3> Following staff training and implementation of the assessment tool, an audit was undertaken which showed: 96% of patients had a nutritional assessment completed within 24 h of admission. 100% of patients requiring an individualised care plan had one formulated. 89% of all patient meals were recorded by catering team. <h3>Conclusion</h3> This simple intervention made a significant improvement in the assessment and management of nutritional risk in the hospice inpatient population compared to the baseline audit prior to the revised policy. Clinical and Catering staff working together has made a positive impact on practice for inpatients. In recognition that people admitted to the hospice are often frailer and more likely to already have established malnutrition, the nutritional tool has now been introduced to the hospice outpatient services. This will hopefully delay the onset of malnutrition in these patients.

A note on optimal point distributions in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.gif" overflow="scroll"><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:msup><mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mrow><mml:mi>s</mml:mi></mml:mrow></mml:msup></mml:math>

2006-10-21
Gerhard Larcher , Friedrich Pillichshammer

Some open problems concerning the star-discrepancy

2003-03-25
Stefan Heinrich

Quasi-Random Sequences and Their Discrepancies

1994-11-01
William J. Morokoff , Russel E. Caflisch
Quasi-random (also called low discrepancy) sequences are a deterministic alternative to random sequences for use in Monte Carlo methods, such as integration and particle simulations of transport processes. The error … Quasi-random (also called low discrepancy) sequences are a deterministic alternative to random sequences for use in Monte Carlo methods, such as integration and particle simulations of transport processes. The error in uniformity for such a sequence of N points in the s-dimensional unit cube is measured by its discrepancy, which is of size $(\log N)^s N^{ - 1} $ for large N, as opposed to discrepancy of size $(\log \log N)^{1/2} N^{ - 1/2} $ for a random sequence (i.e., for almost any randomly chosen sequence). Several types of discrepancies, one of which is new, are defined and analyzed. A critical discussion of the theoretical bounds on these discrepancies is presented. Computations of discrepancies are presented for a wide choice of dimension s, number of points N, and different quasi-random sequences. In particular for moderate or large s, there is an intermediate regime in which the discrepancy of a quasi-random sequence is almost exactly the same as that of a randomly chosen sequence. A simplified proof is given for Woźniakowski's result relating discrepancy and average integration error, and this result is generalized to other measures on function space.
View PDF Chat

Bounds and constructions for the star-discrepancy via <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>δ</mml:mi></mml:math>-covers

2005-08-19
Benjamin Doerr , Michael Gnewuch , Anand Srivastav

Irregularities of distribution. VI

1972-01-01
Wolfgang M. Schmidt

On the Small Ball Inequality in all dimensions

2007-11-10
Dmitriy Bilyk , Michael T. Lacey , Armen Vagharshakyan
View PDF Chat

Optimal Point Sets for Quasi-Monte Carlo Integration of Bivariate Periodic Functions with Bounded Mixed Derivatives

2016-01-01
Aicke Hinrichs , Jens Oettershagen
View PDF Chat

Extreme and periodic $L_2$ discrepancy of plane point sets

2021-01-01
Aicke Hinrichs , Ralph Kritzinger , Friedrich Pillichshammer
We study the extreme and the periodic&nbsp;$L_2$ discrepancy of plane point sets. The extreme discrepancy is based on arbitrary rectangles as test sets whereas the periodic discrepancy uses "periodic intervals", … We study the extreme and the periodic&nbsp;$L_2$ discrepancy of plane point sets. The extreme discrepancy is based on arbitrary rectangles as test sets whereas the periodic discrepancy uses "periodic intervals", which can be seen as intervals on the t
View PDF Chat

MatBuilder

2022-07-01
Loïs Paulin , Nicolas Bonneel , David Cœurjolly +3 more
Many applications ranging from quasi-Monte Carlo integration over optimal control to neural networks benefit from high-dimensional, highly uniform samples. In the case of computer graphics, and more particularly in rendering, … Many applications ranging from quasi-Monte Carlo integration over optimal control to neural networks benefit from high-dimensional, highly uniform samples. In the case of computer graphics, and more particularly in rendering, despite the need for uniformity, several sub-problems expose a low-dimensional structure. In this context, mastering sampling uniformity over projections while preserving high-dimensional uniformity has been intrinsically challenging. This difficulty may explain the relatively small number of mathematical constructions for such samplers. We propose a novel approach by showing that uniformity constraints can be expressed as an integer linear program that results in a sampler with the desired properties. As it turns out, complex constraints are easy to describe by means of stratification and sequence properties of digital nets. Formalized using generator matrix determinants, our new MatBuilder software solves the set of constraints by iterating the linear integer program solver in a greedy fashion to compute a problem-specific set of generator matrices that can be used as a drop-in replacement in the popular digital net samplers. The samplers created by MatBuilder achieve the uniformity of classic low discrepancy sequences. More importantly, we demonstrate the benefit of the unprecedented versatility of our constraint approach with respect to low-dimensional problem structure for several applications.
View PDF Chat

Random Number Generation and Quasi-Monte Carlo Methods

1992-01-01
Harald Niederreiter

Digital Nets and Sequences

2010-09-09
Josef Dick , Friedrich Pillichshammer
Indispensable for students, invaluable for researchers, this comprehensive treatment of contemporary quasi–Monte Carlo methods, digital nets and sequences, and discrepancy theory starts from scratch with detailed explanations of the basic … Indispensable for students, invaluable for researchers, this comprehensive treatment of contemporary quasi–Monte Carlo methods, digital nets and sequences, and discrepancy theory starts from scratch with detailed explanations of the basic concepts and then advances to current methods used in research. As deterministic versions of the Monte Carlo method, quasi–Monte Carlo rules have increased in popularity, with many fruitful applications in mathematical practice. These rules require nodes with good uniform distribution properties, and digital nets and sequences in the sense of Niederreiter are known to be excellent candidates. Besides the classical theory, the book contains chapters on reproducing kernel Hilbert spaces and weighted integration, duality theory for digital nets, polynomial lattice rules, the newest constructions by Niederreiter and Xing and many more. The authors present an accessible introduction to the subject based mainly on material taught in undergraduate courses with numerous examples, exercises and illustrations.