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 an O(n² log n) algorithm that computes the maximum bichromatic discrepancy of rectangles in two dimensions. In addition, we present an O(n² log² n) 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 in JCSS.