Mapping polygons to the grid with small Hausdorff and Fréchet distance

Q.W. Bouts, I. Kostitsyna, M.J. van Kreveld, W. Meulemans, W. Sonke, K.A.B. Verbeek

Research output: Contribution to journalArticleAcademic

113 Downloads (Pure)


We show how to represent a simple polygon P by a grid (pixel-based) polygon Q that is simple and whose Hausdorff or Fréchet distance to P is small. For any simple polygon P, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.
Original languageEnglish
Number of pages33
Publication statusPublished - 21 Jun 2016

Bibliographical note

To appear in European Symposium on Algorithms 2016


  • cs.CG


Dive into the research topics of 'Mapping polygons to the grid with small Hausdorff and Fréchet distance'. Together they form a unique fingerprint.

Cite this