David Dobkin
ABSTRACT
We develop algorithms for computing the discrepancy of point sets in various Euclidean range spaces.
- 1.J. Beck and W.W.L. Chen. Irregularities of Distribution, Cambridge University Press, 1987.Google Scholar
Cross Ref
- 2.R. L. Cook, T. Porter, and L. Carpenter. Distributed ray tracing. Computer Graphics 18 (1984) 137-145. Google ScholarDigital Library
- 3.David P. Dobkin and Don P. Mitchell. Randomedge discrepancy of supersampling patterns. Graphics interface '93, York, Ontario, May, 1993.Google Scholar
- 4.H. Edelsbrunner and L. Guibas. Topologically sweeping an arrangement, j. Cornpui. Sys. Sci. 38 (1989) 165-194. Google ScholarDigital Library
- 5.A. Glassner. An Introduction to Ray Tracing, Academic Press (1989). Google ScholarDigital Library
- 6.J.H. Halton. On the efficiency of certain quasirandora sequences of points in evaluating multidimensional integrals. Num. Math. 2 (1960) 84-90.Google ScholarDigital Library
- 7.J. Hershberger and S. Suri. Offiine maintenance of planar configurations. 2nd ACM/SIAM Syrup. Discrete Algorithms (1991) 32-41. Google ScholarDigital Library
- 8.J. T. Kajiya. The Rendering Equation. Computer Graphics 20 (t986) 143-150. Google ScholarDigital Library
- 9.H. Niederreiter. Methods for estimating discrepancy. In Applications of Number Theory to Numerical Analysis, S.K. Zaremba, ed., Academic Press (1971) 203-236.Google Scholar
- 10.M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J_ Comput. Sys. Sci. 23 ( 198 l) 166-204.Google ScholarCross Ref
- 11.M. Overmars and C.K. Yap. New upper bounds in Klee's measure problem. SIAM J. Comput. 20 (1991) 1034-1045. Google ScholarDigital Library
- 12.K.F. Roth. On irregularities of distribution. Mathemalika i (1954) 73-79.Google Scholar
- 13.W.M. Schmidt. Irregularities of distribution VIi. Acla Arith. 21 (1972) 45-50.Google ScholarCross Ref
- 14.Tony T. Warnock. Computational investigations of low-discrepancy point sets. In Applications of Number Theory to Numerical Analysis, S.K. Zaremba, ed., Academic Press (1971) 319-344.Google Scholar
Index Terms
- Computing the discrepancy
Recommendations
Computing the discrepancy with applications to supersampling patterns
Patterns used for supersampling in graphics have been analyzed from statistical and signal-processing viewpoints. We present an analysis based on a type of isotropic discrepancy—how good patterns are at estimating the area in a region of defined type. ...
Tight hardness results for minimizing discrepancy
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithmsIn the Discrepancy problem, we are given M sets {S1,..., SM} on N elements. Our goal is to find an assignment χ of {−1, + 1} values to elements, so as to minimize the maximum discrepancy maxj | ΣiεSj χ(i)|. Recently, Bansal gave an efficient algorithm ...
Gaussian discrepancy: A probabilistic relaxation of vector balancing
AbstractWe introduce a novel relaxation of combinatorial discrepancy called Gaussian discrepancy, whereby binary signings are replaced with correlated standard Gaussian random variables. This relaxation effectively reformulates an optimization ...
Comments