License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.22
URN: urn:nbn:de:0030-drops-63738
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6373/
Go to the corresponding LIPIcs Volume Portal

Bouts, Quirijn W. ; Irina Kostitsyna, Irina ; van Kreveld, Marc ; Meulemans, Wouter ; Sonke, Willem ; Verbeek, Kevin

Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance

pdf-format:
LIPIcs-ESA-2016-22.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{bouts_et_al:LIPIcs:2016:6373,
  author =	{Quirijn W. Bouts and Irina Irina Kostitsyna and Marc van Kreveld and Wouter Meulemans and Willem Sonke and Kevin Verbeek},
  title =	{{Mapping Polygons to the Grid with Small Hausdorff and Fr{\'e}chet Distance}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6373},
  URN =		{urn:nbn:de:0030-drops-63738},
  doi =		{10.4230/LIPIcs.ESA.2016.22},
  annote =	{Keywords: grid mapping, Hausdorff distance, Fr{\'e}chet distance, digital geometry}
}

Keywords: grid mapping, Hausdorff distance, Fréchet distance, digital geometry
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI