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

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

Research output: Contribution to conferenceAbstractAcademic

38 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
Pages247-250
Number of pages4
Publication statusPublished - 1 Apr 2016
Event32nd European Workshop on Computational Geometry (EuroCG 2016) - Lugano, Switzerland
Duration: 30 Mar 20161 Apr 2016
Conference number: 32
http://www.eurocg2016.usi.ch/

Workshop

Workshop32nd European Workshop on Computational Geometry (EuroCG 2016)
Abbreviated titleEuroCG 2016
CountrySwitzerland
CityLugano
Period30/03/161/04/16
Internet address

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