QUASI-MONTE-CARLO METHODS AND THE DISPERSION OF POINT SEQUENCES

Quasi-Monte-Carlo methods are well known for solving different problem s of numerical analysis such as integration, optimization, etc. The er ror estimates for global optimization depend on the dispersion of the point sequence with respect to balls. In general, the dispersion of a point set with respect to various classes of range spaces, like balls, squares, triangles, axis-parallel and arbitrary rectangles, spherical caps and slices, is the area of the largest empty range, and it is a measure for the distribution of the points. The main purpose of our pa per is to give a survey about this topic, including some folklore resu lts. Furthermore, we prove several properties of the dispersion, gener alizing investigations of Niederreiter and others concerning balls. Fo r several well-known uniformly distributed point sets, we estimate the dispersion with respect to triangles, and we also compare them comput ationally. For the dispersion with respect to spherical slices, we men tion an application to the polygonal approximation of curves in space.