Summary
Many experiments in computer graphics imply that the average quality of quasi-Monte Carlo integro-approximation is improved as the minimal distance of the point set grows. While the definition of (t, m, s)-nets in base b guarantees extensive stratification properties, which are best for t = 0, sampling points can still lie arbitrarily close together. We remove this degree of freedom, report results of two computer searches for (0, m, 2)-nets in base 2 with maximized minimum distance, and present an inferred construction for general m. The findings are especially useful in computer graphics and, unexpectedly, some (0, m, 2)-nets with the best minimum distance properties cannot be generated in the classical way using generator matrices.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Cook, L. Carpenter, and E. Catmull. The REYES Image Rendering Architecture. In Computer Graphics (SIGGRAPH ’87 Conference Proceedings), pages 95–102, July 1987.
R. Cranley and T. Patterson. Randomization of number theoretic methods for multiple integration. SIAM Journal on Numerical Analysis, 13:904–914, 1976.
R. Cook, T. Porter, and L. Carpenter. Distributed Ray Tracing. In Computer Graphics (SIGGRAPH ’84 Conference Proceedings), pages 137–145, 1984.
I. Friedel and A. Keller. Fast Generation of Randomized Low-Discrepancy Point Sets. In H. Niederreiter, K. Fang, and F. Hickernell, editors, Monte Carlo and Quasi-Monte Carlo Methods 2000, pages 257–273. Springer, 2002.
A. Glassner. Principles of Digital Image Synthesis. Morgan Kaufmann, 1995.
P. Haeberli and K. Akeley. The Accumulation Buffer: Hardware Support for High-Quality Rendering. In Computer Graphics (SIGGRAPH ’90 Conference Proceedings), pages 309–318, 1990.
A. Keller. Strictly Deterministic Sampling Methods in Computer Graphics. SIGGRAPH 2003 Course Notes, Course #44: Monte Carlo Ray Tracing, 2003.
A. Keller. Trajectory Splitting by Restricted Replication. Monte Carlo Methods and Applications, 10(3–4):321–329, 2004.
A. Keller. Myths of Computer Graphics. In H. Niederreiter, editor, Monte Carlo and Quasi-Monte Carlo Methods 2004, pages 217–243. Springer, 2006.
A. Keller and W. Heidrich. Interleaved Sampling. In K. Myszkowski and S. Gortler, editors, Rendering Techniques 2001 (Proc. 12th Eurographics Workshop on Rendering), pages 269–276. Springer, 2001.
T. Kollig and A. Keller. Efficient Multidimensional Sampling. Computer Graphics Forum, 21(3):557–563, September 2002.
G. Larcher and F. Pillichshammer. Walsh Series Analysis of the L2-Discrepancy of Symmetrisized Point Sets. Monatsh. Math., 132:1–18, 2001.
H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, 1992.
A. Owen. Randomly Permuted (t, m, s)-Nets and (t, s)-Sequences. In H. Niederreiter and P. Shiue, editors, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, volume 106 of Lecture Notes in Statistics, pages 299–315. Springer, 1995.
A. Owen. Monte Carlo Extension of Quasi-Monte Carlo. In Winter Simulation Conference, pages 571–577. IEEE Press, 1998.
F. Panneton. Construction d’ensembles de points basé sur une récurrence linéaire dans un corps fini de caractéristique 2 pour la simulation Monte Carlo et l’intégration quasi-Monte Carlo. PhD thesis, Université de Montréal, 2004.
G. Pirsic and W. Ch. Schmid. Calculation of the quality parameter of digital nets and application to their construction. J. Complexity, 17(4):827–839, 2001.
H. Press, S. Teukolsky, T. Vetterling, and B. Flannery. Numerical Recipes in C. Cambridge University Press, 1992.
T. Rolfe. Optimal Queens - A classical problem solved by backtracking. Dr. Dobb’s Journal, 30(372), May 2005.
I. Sobol’. On the Distribution of Points in a Cube and the approximate Evaluation of Integrals. Zh. vychisl. Mat. mat. Fiz., 7(4):784–802, 1967.
C. Wächter and A. Keller. Efficient Simultaneous Simulation of Markov Chains. In A. Keller, S. Heinrich, and H. Niederreiter, editors, Monte Carlo and Quasi-Monte Carlo Methods 2006, in this volume. Springer, 2007.
J. Yellot. Spectral Consequences of Photoreceptor Sampling in the Rhesus Retina. Science, 221:382–385, 1983.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grünschloß, L., Hanika, J., Schwede, R., Keller, A. (2008). (t, m, s)-Nets and Maximized Minimum Distance. In: Keller, A., Heinrich, S., Niederreiter, H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2006. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74496-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-74496-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74495-5
Online ISBN: 978-3-540-74496-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)