The Hausdorff core problem on simple polygons

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}))\).

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.