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

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

doi:10.4230/LIPIcs.ESA.2016.22

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 language	English
Title of host publication	24th Annual European Symposium on Algorithms (ESA 2016)
Editors	Piotr Sankowski, Christos Zaroliagis
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Pages	22:1-22:16
ISBN (Print)	978-3-95977-015-6
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2016.22
Publication status	Published - 18 Aug 2016

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume	57
ISSN (Print)	1868-8969

Keywords

grid mapping
Hausdorff distance
Fréchet distance
digital geometry

Access to Document

10.4230/LIPIcs.ESA.2016.22Licence: CC BY

22Final published version, 671 KBLicence: CC BY

Cite this

Bouts, Q. W., Kostitsyna, I. I., Kreveld, M. V., Meulemans, W., Sonke, W., & Verbeek, K. (2016). Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. In P. Sankowski, & C. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms (ESA 2016) (pp. 22:1-22:16). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ESA.2016.22

Bouts, Quirijn W. ; Kostitsyna, Irina Irina ; Kreveld, Marc van et al. / Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. 24th Annual European Symposium on Algorithms (ESA 2016). editor / Piotr Sankowski ; Christos Zaroliagis. Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. pp. 22:1-22:16 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{2befb32bee9f490e9cd5b8b9c679fd5a,

title = "Mapping Polygons to the Grid with Small Hausdorff and Fr{\'e}chet Distance",

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{\'e}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{\'e}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.",

keywords = "grid mapping, Hausdorff distance, Fr{\'e}chet distance, digital geometry",

author = "Bouts, {Quirijn W.} and Kostitsyna, {Irina Irina} and Kreveld, {Marc van} and Wouter Meulemans and Willem Sonke and Kevin Verbeek",

year = "2016",

month = aug,

day = "18",

doi = "10.4230/LIPIcs.ESA.2016.22",

language = "English",

isbn = "978-3-95977-015-6",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik",

pages = "22:1--22:16",

editor = "Piotr Sankowski and Christos Zaroliagis",

booktitle = "24th Annual European Symposium on Algorithms (ESA 2016)",

}

Bouts, QW, Kostitsyna, II, Kreveld, MV, Meulemans, W, Sonke, W & Verbeek, K 2016, Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. in P Sankowski & C Zaroliagis (eds), 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 57, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 22:1-22:16. https://doi.org/10.4230/LIPIcs.ESA.2016.22

Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. / Bouts, Quirijn W.; Kostitsyna, Irina Irina; Kreveld, Marc van et al.
24th Annual European Symposium on Algorithms (ESA 2016). ed. / Piotr Sankowski; Christos Zaroliagis. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. p. 22:1-22:16 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 57).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Bouts, Quirijn W.

AU - Kostitsyna, Irina Irina

AU - Kreveld, Marc van

AU - Meulemans, Wouter

AU - Sonke, Willem

AU - Verbeek, Kevin

PY - 2016/8/18

Y1 - 2016/8/18

N2 - 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.

AB - 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.

KW - grid mapping

KW - Hausdorff distance

KW - Fréchet distance

KW - digital geometry

U2 - 10.4230/LIPIcs.ESA.2016.22

DO - 10.4230/LIPIcs.ESA.2016.22

M3 - Conference contribution

SN - 978-3-95977-015-6

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 22:1-22:16

BT - 24th Annual European Symposium on Algorithms (ESA 2016)

A2 - Sankowski, Piotr

A2 - Zaroliagis, Christos

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

CY - Dagstuhl, Germany

ER -

Bouts QW, Kostitsyna II, Kreveld MV, Meulemans W, Sonke W, Verbeek K. Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. In Sankowski P, Zaroliagis C, editors, 24th Annual European Symposium on Algorithms (ESA 2016). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 2016. p. 22:1-22:16. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ESA.2016.22

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

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this