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

We present a general approach to solving the minimizing disagreement

problem for geometric hypotheses with finite VC-dimension. These

results also imply efficient agnostic-PAC learning of these hypotheses

classes. In particular we give anO(nmin(alpha + 1/2, 2k-1) logn)

algorithm that solves the m.d.p. for two-dimensional convexk-gon hypotheses (wherealphais the VC-dimension of the implied

set system,kis constant), and anO(n3k-1 logn) algorithm

for three-dimensional convexk-hedra hypotheses. We extend these

results to handle unions ofk-gons and give an approach to

approximation algorithms.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/375

[2] http://www.cs.princeton.edu/research/techreps/author/301

[3] ftp://ftp.cs.princeton.edu/techreports/1994/481.ps.gz