Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Ivor van der Hoog; Mees van de Kerkhof; Marc van Kreveld; Maarten Löffler; Frank Staals; Jérôme Urhausen; Jordi Vermeulen

doi:10.1007/978-3-030-83508-8_45

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Ivor van der Hoog
, Mees van de Kerkhof
, Marc van Kreveld
, Maarten Löffler
, Frank Staals
, Jérôme Urhausen
, Jordi Vermeulen

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

Abstract

We study a problem motivated by digital geometry: given a set of disjoint geometric regions, assign each region Ri a set of grid cells Pi, so that Pi is connected, similar to Ri, and does not touch any grid cell assigned to another region. Similarity is measured using the Hausdorff distance. We analyze the achievable Hausdorff distance in terms of the number of input regions, and prove asymptotically tight bounds for several classes of input regions.

Original language	English
Title of host publication	Algorithms and Data Structures
Subtitle of host publication	17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings
Editors	Anna Lubiw, Mohammad Salavatipour, Meng He
Publisher	Springer
Pages	627-640
Edition	1
ISBN (Electronic)	978-3-030-83508-8
ISBN (Print)	978-3-030-83507-1
DOIs	https://doi.org/10.1007/978-3-030-83508-8_45
Publication status	Published - 2021

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12808
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Computational geometry
Digital geometry
Hausdorffdistance
Simple polygons

Access to Document

10.1007/978-3-030-83508-8_45

978-3-030-83508-8_45Final published version, 510 KBLicence: Taverne

Cite this

van der Hoog, I., van de Kerkhof, M., van Kreveld, M., Löffler, M., Staals, F., Urhausen, J., & Vermeulen, J. (2021). Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (1 ed., pp. 627-640). (Lecture Notes in Computer Science; Vol. 12808). Springer. https://doi.org/10.1007/978-3-030-83508-8_45

van der Hoog, Ivor ; van de Kerkhof, Mees ; van Kreveld, Marc et al. / Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance. Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. editor / Anna Lubiw ; Mohammad Salavatipour ; Meng He. 1. ed. Springer, 2021. pp. 627-640 (Lecture Notes in Computer Science).

@inproceedings{42c2743f239541ff911546ccf681762f,

title = "Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance",

abstract = "We study a problem motivated by digital geometry: given a set of disjoint geometric regions, assign each region Ri a set of grid cells Pi, so that Pi is connected, similar to Ri, and does not touch any grid cell assigned to another region. Similarity is measured using the Hausdorff distance. We analyze the achievable Hausdorff distance in terms of the number of input regions, and prove asymptotically tight bounds for several classes of input regions.",

keywords = "Computational geometry, Digital geometry, Hausdorffdistance, Simple polygons",

author = "\{van der Hoog\}, Ivor and \{van de Kerkhof\}, Mees and \{van Kreveld\}, Marc and Maarten L{\"o}ffler and Frank Staals and J{\'e}r{\^o}me Urhausen and Jordi Vermeulen",

year = "2021",

doi = "10.1007/978-3-030-83508-8\_45",

language = "English",

isbn = "978-3-030-83507-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "627--640",

editor = "Lubiw, \{Anna \} and Salavatipour, \{Mohammad \} and He, \{Meng \}",

booktitle = "Algorithms and Data Structures",

edition = "1",

}

van der Hoog, I, van de Kerkhof, M, van Kreveld, M , Löffler, M , Staals, F, Urhausen, J & Vermeulen, J 2021, Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance. in A Lubiw, M Salavatipour & M He (eds), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. 1 edn, Lecture Notes in Computer Science, vol. 12808, Springer, pp. 627-640. https://doi.org/10.1007/978-3-030-83508-8_45

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance. / van der Hoog, Ivor; van de Kerkhof, Mees; van Kreveld, Marc et al.
Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. ed. / Anna Lubiw; Mohammad Salavatipour; Meng He. 1. ed. Springer, 2021. p. 627-640 (Lecture Notes in Computer Science; Vol. 12808).

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

TY - GEN

T1 - Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

AU - van der Hoog, Ivor

AU - van de Kerkhof, Mees

AU - van Kreveld, Marc

AU - Löffler, Maarten

AU - Staals, Frank

AU - Urhausen, Jérôme

AU - Vermeulen, Jordi

PY - 2021

Y1 - 2021

N2 - We study a problem motivated by digital geometry: given a set of disjoint geometric regions, assign each region Ri a set of grid cells Pi, so that Pi is connected, similar to Ri, and does not touch any grid cell assigned to another region. Similarity is measured using the Hausdorff distance. We analyze the achievable Hausdorff distance in terms of the number of input regions, and prove asymptotically tight bounds for several classes of input regions.

AB - We study a problem motivated by digital geometry: given a set of disjoint geometric regions, assign each region Ri a set of grid cells Pi, so that Pi is connected, similar to Ri, and does not touch any grid cell assigned to another region. Similarity is measured using the Hausdorff distance. We analyze the achievable Hausdorff distance in terms of the number of input regions, and prove asymptotically tight bounds for several classes of input regions.

KW - Computational geometry

KW - Digital geometry

KW - Hausdorffdistance

KW - Simple polygons

U2 - 10.1007/978-3-030-83508-8_45

DO - 10.1007/978-3-030-83508-8_45

M3 - Conference contribution

SN - 978-3-030-83507-1

T3 - Lecture Notes in Computer Science

SP - 627

EP - 640

BT - Algorithms and Data Structures

A2 - Lubiw, Anna

A2 - Salavatipour, Mohammad

A2 - He, Meng

PB - Springer

ER -

van der Hoog I, van de Kerkhof M, van Kreveld M , Löffler M , Staals F, Urhausen J et al. Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance. In Lubiw A, Salavatipour M, He M, editors, Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. 1 ed. Springer. 2021. p. 627-640. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-83508-8_45

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this