Mapping Points to the Grid with Bounded Hausdorff Distance

EasyChair Preprint no. 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: computational geometry, Digital Geometry, flow algorithm, Hausdorff distance, Pixels, 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 no. 12828},

  year = {EasyChair, 2024}}