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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
83 Downloads (Pure)


We show how to represent a simple polygon P by a (pixel-based) grid 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
Title of host publicationProc. 24th Annual European Symposium on Algorithms (ESA)
EditorsP. Sankowski, C. Zaroliagis
Place of Publications.l.
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)978-3-95977-015-6
Publication statusPublished - 1 Aug 2016
Event24th Annual European Symposium on Algorithms (ESA 2016) - Aarhus, Denmark
Duration: 22 Aug 201624 Aug 2016
Conference number: 24

Publication series

NameLeibniz International Proceedings in Informatics


Conference24th Annual European Symposium on Algorithms (ESA 2016)
Abbreviated titleESA 2016
Internet address


  • Digital geometry
  • Fréchet distance
  • Grid mapping
  • Hausdorff distance


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