Download PDFOpen PDF in browserMapping Points to the Grid with Bounded Hausdorff DistanceEasyChair Preprint 128289 pages•Date: March 29, 2024AbstractWe consider the problem of representing a set of m points using pixels on a grid with bounded Hausdorff distance. We prove that optimizing the problem is NP-complete. Additionally, we present a constant factor approximation algorithm with running time in O(m^2 log δ^∗ / log m), where δ^∗ is the Hausdorff distance in an optimal solution, as well as a slower algorithm with a constant additive error. Keyphrases: Digital Geometry, Hausdorff distance, Pixels, computational geometry, flow algorithm, point sets, similarity measure, unit grid
|