Computing the Discrepancy with Applications to Supersampling Patterns

David P. Dobkin, David Eppstein, Don P. Mitchell

Research output: Contribution to journalArticlepeer-review

59 Scopus citations


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. We present algorithms for computing discrepancy relative to regions that are defined by rectangles, halfplanes, and higher-dimensional figures. Experimental evidence shows that popular supersampling patterns have discrepancies with better asymptotic behavior than random sampling, which is not inconsistent with theoretical bounds on discrepancy.

Original languageEnglish (US)
Pages (from-to)354-376
Number of pages23
JournalACM Transactions on Graphics
Issue number4
StatePublished - Oct 1996

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design


  • Algorithms
  • Discrepancy
  • Experimentation
  • F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-geometrical problems and computations
  • I.3.3 [Computer Graphics]. Picture/Image Generation-antialiasing
  • Ray-tracing


Dive into the research topics of 'Computing the Discrepancy with Applications to Supersampling Patterns'. Together they form a unique fingerprint.

Cite this