Computing the Hausdorff core of simple polygons

by Robert Fraser

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

Joint work with Reza Dorrigiv, Stephane Durocher, 
Arash Farzan, Alejandro Lopez-Ortiz, J. Ian Munro, Patrick Nicholson, 
Alejandro Salinger and Matthew Skala