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.

Crossref

Google Scholar

[11]

M. Overmars and C.K. Yap. New upper bounds in Klee's measure problem. SIAM J. Comput. 20 (1991) 1034-1045.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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

Cited By

View all

Chakraborty DKovvali NPapandreou-Suppappola AChattopadhyay A(2014)An adaptive learning damage estimation method for structural health monitoringJournal of Intelligent Material Systems and Structures10.1177/1045389X1452253126:2(125-143)Online publication date: 14-Apr-2014
https://doi.org/10.1177/1045389X14522531
Dang TShalev N(2014)Test Coverage Estimation Using Threshold AcceptingAutomated Technology for Verification and Analysis10.1007/978-3-319-11936-6_9(115-128)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11936-6_9
Wong TLuk WHeng P(2011)Sampling with Hammersley and Halton PointsGraphics Tools---The jgt Editors' Choice10.1201/b10628-32(255-270)Online publication date: 11-Mar-2011
https://doi.org/10.1201/b10628-32
Show More Cited By

Index Terms

Computing the discrepancy
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

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 algorithms

In the Discrepancy problem, we are given M sets {S₁,..., S_M} on N elements. Our goal is to find an assignment χ of {−1, + 1} values to elements, so as to minimize the maximum discrepancy max_j | Σ_iεSj χ(i)|. Recently, Bansal gave an efficient algorithm ...
Gaussian discrepancy: A probabilistic relaxation of vector balancing
Abstract
We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '93: Proceedings of the ninth annual symposium on Computational geometry

July 1993

406 pages

ISBN:0897915828

DOI:10.1145/160985

Chairman:
Chee Yap

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

9SCG93

Sponsor:

9SCG93: Ninth Symposium on Computational Geometry

May 18 - 21, 1993

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
568
Total Downloads

Downloads (Last 12 months)116
Downloads (Last 6 weeks)14

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chakraborty DKovvali NPapandreou-Suppappola AChattopadhyay A(2014)An adaptive learning damage estimation method for structural health monitoringJournal of Intelligent Material Systems and Structures10.1177/1045389X1452253126:2(125-143)Online publication date: 14-Apr-2014
https://doi.org/10.1177/1045389X14522531
Dang TShalev N(2014)Test Coverage Estimation Using Threshold AcceptingAutomated Technology for Verification and Analysis10.1007/978-3-319-11936-6_9(115-128)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11936-6_9
Wong TLuk WHeng P(2011)Sampling with Hammersley and Halton PointsGraphics Tools---The jgt Editors' Choice10.1201/b10628-32(255-270)Online publication date: 11-Mar-2011
https://doi.org/10.1201/b10628-32
Dang TNahhal T(2009)Coverage-guided test generation for continuous and hybrid systemsFormal Methods in System Design10.5555/1519231.151926734:2(183-213)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.5555/1519231.1519267
Lappas TArai BPlatakis MKotsakos DGunopulos DElder JFogelman FFlach PZaki M(2009)On burstiness-aware search for document sequencesProceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/1557019.1557075(477-486)Online publication date: 28-Jun-2009
https://dl.acm.org/doi/10.1145/1557019.1557075
Dang TNahhal T(2009)Coverage-guided test generation for continuous and hybrid systemsFormal Methods in System Design10.1007/s10703-009-0066-034:2(183-213)Online publication date: 7-Feb-2009
https://doi.org/10.1007/s10703-009-0066-0
Nahhal TDang T(2007)Test coverage for continuous and hybrid systemsProceedings of the 19th international conference on Computer aided verification10.5555/1770351.1770414(449-462)Online publication date: 3-Jul-2007
https://dl.acm.org/doi/10.5555/1770351.1770414
Nahhal TDang T(2007)Test Coverage for Continuous and Hybrid SystemsComputer Aided Verification10.1007/978-3-540-73368-3_47(449-462)Online publication date: 2007
https://doi.org/10.1007/978-3-540-73368-3_47
Agarwal DPhillips JVenkatasubramanian S(2006)The hunting of the bumpProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm10.5555/1109557.1109683(1137-1146)Online publication date: 22-Jan-2006
https://dl.acm.org/doi/10.5555/1109557.1109683
Quinn JLangbein FMartin RElber G(2006)Density-controlled sampling of parametric surfaces using adaptive space-filling curvesProceedings of the 4th international conference on Geometric Modeling and Processing10.1007/11802914_33(465-484)Online publication date: 26-Jul-2006
https://dl.acm.org/doi/10.1007/11802914_33
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Computing the discrepancy with applications to supersampling patterns

Tight hardness results for minimizing discrepancy

Gaussian discrepancy: A probabilistic relaxation of vector balancing