The Hausdorff core problem on simple polygons

  • Reza Dorrigiv Dalhousie University
  • Stephane Durocher University of Manitoba
  • Arash Farzan Max-Planck-Institut f\"ur Informatik
  • Robert Fraser University of Manitoba
  • Alejandro Lopez-Ortiz University of Waterloo
  • J. Ian Munro University of Waterloo
  • Alejandro Salinger University of Waterloo
  • Matthew Skala University of Manitoba

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}))\).
Published
2014-02-17
How to Cite
Dorrigiv, R., Durocher, S., Farzan, A., Fraser, R., Lopez-Ortiz, A., Munro, J. I., Salinger, A., & Skala, M. (2014). The Hausdorff core problem on simple polygons. Journal of Computational Geometry, 5(1), 14–40. https://doi.org/10.20382/jocg.v5i1a2
Section
Articles

Most read articles by the same author(s)