### The Hausdorff core problem on simple polygons

Reza Dorrigiv, Stephane Durocher, Arash Farzan, Robert Fraser, Alejandro Lopez-Ortiz, J. Ian Munro, Alejandro Salinger, Matthew Skala

#### Abstract

A polygon $Q$ is a $k$-bounded Hausdorff Core of a polygon $P$ if $P$ contains $Q$, $Q$ is convex, and the Hausdorff distance between $P$ and $Q$ is at most $k$. A Hausdorff Core of $P$ is a $k$-bounded Hausdorff Core of $P$ with the minimum possible value of $k$, which we denote $k_{\min}$. Given any $k$ and any $\varepsilon\gt 0$, we describe an algorithm for computing a $k'$-bounded Hausdorff Core (if one exists) in $O(n^3+n^2\varepsilon^{-4}(\log n+ \varepsilon^{-2}))$ time, where $k'\lt k+d_{\text{rad}}\cdot\varepsilon$ and $d_{\text{rad}}$ is the radius of the smallest disc that encloses $P$ and whose center is in $P$. We use this solution to provide an approximation algorithm for the optimization Hausdorff Core problem which results in a solution of size $k_{\min}+d_{\text{rad}}\cdot\varepsilon$ in $O(\log(\varepsilon^{-1})(n^3+n^2\varepsilon^{-4}(\log n+ \varepsilon^{-2})))$ time. Finally, we describe an approximation scheme for the $k$-bounded Hausdorff Core problem which, given a polygon $P$, a distance $k$, and any $\varepsilon\gt 0$, answers true if there is a $((1+\varepsilon)k)$-bounded Hausdorff Core and false if there is no $k$-bounded Hausdorff Core. The running time of the approximation scheme is in $O(n^3+n^2\varepsilon^{-4}(\log n+ \varepsilon^{-2}))$.

#### Full Text:

PDF

DOI: http://dx.doi.org/10.20382/jocg.v5i1a2

ISSN: 1920-180X