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

Report ID:

TR-563-95

Authors:

Date:

November 1995

Pages:

8

Download Formats:

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+

½ , 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-1logn)

algorithm for convexk-hedra hypotheses in three dimensions. We

extend these results to handle unions ofk-gons and give an

approach to approximation algorithms.