2026-07-25T06:45:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6373 2024-03-06T10:38:05Z ddc:004 open_access

Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance Bouts, Quirijn W. Irina Kostitsyna, Irina van Kreveld, Marc Meulemans, Wouter Sonke, Willem Verbeek, Kevin grid mapping Hausdorff distance Fréchet distance digital geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Quirijn W. Bouts and Irina Irina Kostitsyna and Marc van Kreveld and Wouter Meulemans and Willem Sonke and Kevin Verbeek 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.22 urn:nbn:de:0030-drops-63738 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode