Download PDFOpen PDF in browserMapping Points to the Grid with Bounded Hausdorff DistanceEasyChair Preprint no. 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: computational geometry, Digital Geometry, flow algorithm, Hausdorff distance, Pixels, point sets, similarity measure, unit grid
|