Presented at *SPIE Conf. Computational Imaging*, January 24, 2003, Santa Clara

## Quasi-Monte Carlo – halftoning in high dimensions?

Kenneth M. Hanson

*Los Alamos National Laboratory*
### Abstract

The goal in Quasi-Monte Carlo (QMC) is to improve the accuracy of integrals estimated by the Monte Carlo
technique through a suitable speci.cation of the sample point set. Indeed, the errors from N samples typically
drop as 1/N with QMC, which is much better than the 1/sqrt(N) dependence obtained with Monte Carlo estimates
based on random point sets. The heuristic reasoning behind selecting QMC point sets is similar to that in
halftoning (HT), that is, to spread the points out as evenly as possible, consistent with the desired point density.
I will outline the parallels between QMC and HT, and describe an HT-inspired algorithm for generating a
sample set with uniform density, which yields smaller integration errors than standard QMC algorithms in two
dimensions.

**Keywords:** Quasi-Monte Carlo, Monte Carlo integration, low-discrepancy sequences, Halton sequence, Sobel
sequence, halftoning, direct binary search, minimum visual discrepancy, Voronoi analysis

Viewgraphs for this paper (pdf, 515 KB)

Send e-mail to author at kmh@hansonhub.com