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 |
Available under License Creative Commons: Attribution International Public License 4.0.
Download (688kB) | Preview
Export
Downloads
Downloads per month over past year
Metadata
MetadataActions (login required)
Admin Login