Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-467-94

Authors:

Date:

September 1994

Pages:

38

Download Formats:

Computing the maximum bichromatic discrepancy is an interesting

theoretical problem with important applications in computational

learning theory, computational geometry and computer graphics. In

this paper we give algorithms to compute the maximum bichromatic

discrepancy for simple geometric ranges, including rectangles and

halfspaces. Our main result is anO(n2 logn) algorithm that

computes the maximum bichromatic discrepancy of rectangles in two

dimensions. In addition, we present anO(n2 log2n) algorithm

that computes the maximum numerical discrepancy of rectangles in two

dimensions, and we give extensions to other discrepancy problems.

- This technical report will be published as
- Computing the Maximum Bichromatic Discrepancy, with Applications

to Computer Graphics and Machine Learning. David

P. Dobkin, Dimitrios Gunopulos and Wolfgang Maass,

to appear inJCSS.