The Maximum Discrepancy of Simple Geometric Ranges
Report ID:
TR-480-94
Authors:
Date:
November 1994
Pages:
12
Download Formats:
Abstract:
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 an
O(nmin(alpha + 1/2, 2k-1) log n)
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.