Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-480-94
The Maximum Discrepancy of Simple Geometric Ranges
Authors: Dobkin, David P., Gunopulos, Dimitrios
Date:December 1994
Pages:12
Download Formats: [Postscript]
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.