# 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 $$R_i$$ a set of grid cells $$P_i$$, so that $$P_i$$ is connected, similar to $$R_i$$, 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.

# Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Proc. 2021 WADS Algorithms and Data Structures Symposium, 2021

@incollection{pixelpolygons2021,
author = {Hoog van der, Ivor and van der Kerkhof, Mees and van Kreveld, Marc and
L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me
and Vermeulen, Jordi L.},
title = {Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance},
booktitle = {Proc. 2021 WADS Algorithms and Data Structures Symposium},
series = {LNCS},
year = {2021},
publisher = {Springer},
category = {other},
pages = {627--640},
doi = {10.1007/978-3-030-83508-8_45},
url = {https://doi.org/10.1007/978-3-030-83508-8_45},
}


# Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

@article{pixelpolygons_eurocg,
author = {Hoog van der, Ivor and van der Kerkhof, Mees and van Kreveld, Marc and
L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me
and Vermeulen, Jordi L.},
title = {Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance},
journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
year = {2021},
location = {St. Petersburg, Russia (online)},
numpages = {7},
category = {other},
project = {pixelpolygons2021},