Mapping Points to the Grid with Bounded Hausdorff Distance

EasyChair Preprint 12828

Abstract

We 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

@booklet{EasyChair:12828,
  author    = {Maarten Löffler and Jérôme Urhausen},
  title     = {Mapping Points to the Grid with Bounded Hausdorff Distance},
  howpublished = {EasyChair Preprint 12828},
  year      = {EasyChair, 2024}}