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

Bouts, Q. W., Kostitsyna, I., van Kreveld, M., Meulemans, W., Sonke, W. & Verbeek, K. Mapping polygons to the grid with small Hausdorff and Fréchet distance. In: P. Sankowski & C. Zaroliagis (Eds.), 24rd Annual European Symposium on Algorithms (ESA 2016). (197:1-197:15). Germany: Dagstuhl Publishing.

Text - Accepted Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (688kB) | Preview


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.

Item Type: Book Section
Uncontrolled Keywords: grid mapping, Hausdorff distance, Fréchet distance, digital geometry
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: School of Informatics > giCentre

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics