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

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 conference › Abstract › Academic

178 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 language	English
Pages	247-250
Number of pages	4
Publication status	Published - 1 Apr 2016
Event	32nd European Workshop on Computational Geometry (EuroCG 2016) - Lugano, Switzerland Duration: 30 Mar 2016 → 1 Apr 2016 Conference number: 32 http://www.eurocg2016.usi.ch/

Workshop

Workshop	32nd European Workshop on Computational Geometry (EuroCG 2016)
Abbreviated title	EuroCG 2016
Country/Territory	Switzerland
City	Lugano
Period	30/03/16 → 1/04/16
Internet address	http://www.eurocg2016.usi.ch/

Access to Document

publisher versionFinal published version, 151 KB

Cite this

@conference{82917b09ab6d411f8c697f17b19d40cb,

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.",

author = "Q.W. Bouts and I. Kostitsyna and {van Kreveld}, M.J. and W. Meulemans and W.M. Sonke and K.A.B. Verbeek",

year = "2016",

month = apr,

day = "1",

language = "English",

pages = "247--250",

note = "32nd European Workshop on Computational Geometry (EuroCG 2016), EuroCG 2016 ; Conference date: 30-03-2016 Through 01-04-2016",

url = "http://www.eurocg2016.usi.ch/",

}

TY - CONF

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

AU - Bouts, Q.W.

AU - Kostitsyna, I.

AU - van Kreveld, M.J.

AU - Meulemans, W.

AU - Sonke, W.M.

AU - Verbeek, K.A.B.

N1 - Conference code: 32

PY - 2016/4/1

Y1 - 2016/4/1

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.

M3 - Abstract

SP - 247

EP - 250

T2 - 32nd European Workshop on Computational Geometry (EuroCG 2016)

Y2 - 30 March 2016 through 1 April 2016

ER -

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

Abstract

Workshop

Access to Document

Fingerprint

Cite this