City Research Online

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

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

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.

Publication Type: Book Section
Publisher Keywords: grid mapping, Hausdorff distance, Fréchet distance, digital geometry
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science > giCentre
URI: http://openaccess.city.ac.uk/id/eprint/15168
[img]
Preview
Text - Accepted Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (688kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login