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. & Verbeek, K. (2016). Mapping polygons to the grid with small Hausdorff and Fréchet distance. In: Sankowski, P. & Zaroliagis, C. (Eds.), 24rd Annual European Symposium on Algorithms (ESA 2016).

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: Conference or Workshop Item (Paper)
Publisher Keywords: grid mapping, Hausdorff distance, Fréchet distance, digital geometry
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science > giCentre
[thumbnail of p197-bouts.pdf]
Preview
Text - Accepted Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (688kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login