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

Report ID:

TR-480-94

Authors:

Date:

November 1994

Pages:

12

Download Formats:

In this paper we give algorithms that compute the maximum bichromatic

discrepancy for simple geometric ranges and consequently solve the

minimizing disagreement problem of machine learning for geometric

hypotheses. The main result, presented in section 3 is anO(nmin(alpha + 1/2, 2k-1) logn)

algorithm that computes the

maximum bichromatic discrepancy w.r.t. $k$-gons in two dimensions

(where $alpha$ is the VC-dimension of the implied set system, $k$ is

constant). This is an application of a general approach to computing

the discrepancy of set systems with finite VC-dimension. We also

present an algorithm for the special case of stripes.