Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance
Files
Publication date
2016-08-18
Authors
Bouts, Quirijn W.
Kostitsyna, Irina Irina
van Kreveld, M.J.
Meulemans, Wouter
Sonke, Willem
Verbeek, Kevin
Editors
Sankowski, Piotr
Zaroliagis, Christos
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
Abstract
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.
Keywords
grid mapping, Hausdorff distance, Fréchet distance, digital geometry
Citation
Bouts, Q W, Kostitsyna, I I, Kreveld, M V, Meulemans, W, Sonke, W & Verbeek, K 2016, Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. in P Sankowski & C Zaroliagis (eds), 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 57, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 22:1-22:16. https://doi.org/10.4230/LIPIcs.ESA.2016.22