The Maximum Discrepancy of Simple Geometric Ranges

Report ID: TR-480-94

---

Author: Gunopulos, Dimitrios / Dobkin, David P.

---

Date: 1994-12-00

---

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(n^{min(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.