Computing the Maximum Bichromatic Discrepancy, with Applications to Computer Graphics and Machine Learning

Abstract:

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