Computing the Maximum Bichromatic Discrepancy with Applications to Computer Graphics and Machine Learning
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. In addition, we give extensions to other discrepancy
This technical report has been published as
- Computing the maximum bichromatic discrepancy, with applications
to computer graphics and machine learning.
David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass, J. of
Computer and System Sciences, vol 52, no. 3,
453-470, June 1996.