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

Report ID:

TR-481-94

Authors:

Date:

November 1994

Pages:

12

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 + 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.