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

Q.W. Bouts, Irina Kostitsyna, M.J. van Kreveld, W. Meulemans, W.M. Sonke, K.A.B. Verbeek

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
48 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationProc. 24th Annual European Symposium on Algorithms (ESA)
EditorsP. Sankowski, C. Zaroliagis
Place of Publications.l.
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-16
ISBN (Electronic)978-3-95977-015-6
DOIs
Publication statusPublished - 1 Aug 2016
Event24th Annual European Symposium on Algorithms (ESA 2016) - Aarhus, Denmark
Duration: 22 Aug 201624 Aug 2016
Conference number: 24
http://conferences.au.dk/algo16/esa/

Publication series

NameLeibniz International Proceedings in Informatics
Volume57

Conference

Conference24th Annual European Symposium on Algorithms (ESA 2016)
Abbreviated titleESA 2016
CountryDenmark
CityAarhus
Period22/08/1624/08/16
Internet address

Keywords

  • Digital geometry
  • Fréchet distance
  • Grid mapping
  • Hausdorff distance

Fingerprint

Dive into the research topics of 'Mapping polygons to the grid with small Hausdorff and Fréchet distance'. Together they form a unique fingerprint.

Cite this