Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance


[.pdf] [Hit return to continue]

Abstract

Given a simple polygon P, we consider the problem of finding a convex polygon Q contained in P that minimizes H(P,Q), where H denotes Hausdorff distance. We call such a polygon Q a Hausdorff core of P. We describe polynomial-time approximations for both the minimization and decision versions of the Hausdorff core problem, and we provide an argument supporting the hardness of the problem.


Bibtex Entry