|
The exponent of discrepancy is at most
Author(s):
Grzegorz
W.
Wasilkowski;
Henryk
Wozniakowski.
Journal:
Math. Comp.
66
(1997),
1125-1132.
MSC (1991):
Primary 11K38, 41A55
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We study discrepancy with arbitrary weights in the norm over the -dimensional unit cube. The exponent of discrepancy is defined as the smallest for which there exists a positive number such that for all and all there exist points with discrepancy at most . It is well known that . We improve the upper bound by showing that 
This is done by using relations between discrepancy and integration in the average case setting with the Wiener sheet measure. Our proof is not constructive. The known constructive bound on the exponent is .
References:
- 1.
- J. Beck and W. W. L. Chen, Irregularities of distribution, Cambridge University Press, Cambridge, 1987. MR 88m:11061
- 2.
- V. A. Bykovskij, On exact order of optimal quadrature formulas for spaces of functions with bounded mixed derivatives, Report of the Dalnevostochnoi Center of Academy of Sciences, Vladivostok, USSR (in Russian), 1985.
- 3.
- B. Chazelle, Geometric discrepancy revisited, 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 392-399. CMP 95:11
- 4.
- D. P. Dobkin and D. P. Mitchell, Random-edge discrepancy of supersampling patterns, Graphics Interface '93, York, Ontario, 1993.
- 5.
- K. K. Frolov, Upper bounds of the discrepancy in metric
, , Dokl. Akad. Nauk SSSR 252 (1980), 805-807. MR 81k:10087 - 6.
- S. Heinrich, Efficient algorithms for computing the
discrepancy, Math. Comp. 65 (1996), 1621-1633. CMP 96:01 - 7.
- S. Heinrich and A. Keller, Quasi-Monte Carlo methods in computer graphics, Part I: The QMC-buffer, Report, Univ. of Kaiserslautern, Dept. Computer Science, Report No.242/1994; Part II: The radiance equation, Report, Univ. of Kaiserslautern, Dept. Computer Science, Report No.243/1994.
- 8.
- H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 80d:65016
- 9.
- -, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Reg. Conf. Series Appl. Math., vol. 63, SIAM, Philadelphia, 1992. MR 93h:65008
- 10.
- K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73-79. MR 16:575c
- 11.
- -, On irregularities of distribution, IV, Acta Arith. 37 (1980), 67-75. MR 82f:10063
- 12.
- I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publication, Oxford, 1994.
- 13.
- V. N. Temlyakov, Approximation of functions with bounded mixed derivatives, Proc. Steklov Inst. Math., Moscow, 1989. MR 90e:00007
- 14.
- G. W. Wasilkowski and H. Wo\'{z}niakowski, Explicit cost bounds of algorithms for multivariate tensor product problems, J. Complexity 11 (1995), 1-56. MR 95k:65138
- 15.
- H. Wo\'{z}niakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185-194. MR 91i:65224
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(1991):
11K38, 41A55
Retrieve articles in all Journals with MSC
(1991):
11K38, 41A55
Additional Information:
Grzegorz
W.
Wasilkowski
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506
Email:
greg@cs.engr.uky.edu
Henryk
Wozniakowski
Affiliation:
Department of Computer Science, Columbia University, New York, New York 10027 and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
Email:
henryk@cs.columbia.edu
DOI:
10.1090/S0025-5718-97-00824-7
PII:
S 0025-5718(97)00824-7
Keywords:
Discrepancy,
multivariate integration,
average case
Received by editor(s):
December 20, 1995
Received by editor(s) in revised form:
May 1, 1996
Additional Notes:
The first author was partially supported by the National Science Foundation under Grant CCR-9420543, and the second by the National Science Foundation and the Air Force Office of Scientific Research
Copyright of article:
Copyright
1997,
American Mathematical Society
|